(*

Little Shop of Flowers (IOI 1999)
Copyright (C) 2000 Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


 

Il problema viene risolto mediante programmazione dinamica, e piu`
precisamente riducendo il problema di disporre ottimalmente mazzi di fiori
m_1,...,m_r in vasi v_1,...,v_s con s>=r al problema di disporre ottimalmente
mazzi m_t,...,m_r nei vasi v_u,...,v_s con 1<=t<=r e 1<=u<=s.

*)

{$R+}

PROGRAM Shop;

CONST
	MAXFIORI = 100;
	MAXVASI = 100;

VAR
	M: array [1..MAXFIORI, 1..MAXVASI] of Integer;
		(* Tabella riempita tramite programmazione dinamica. *)
	A: array [1..MAXFIORI, 1..MAXVASI]  of Integer;
		(* Valori estetici per ogni tipo di mazzo e di vaso. *)
	U: array [1..MAXFIORI, 1..MAXVASI]  of Boolean;
		(* Matrice di valori booleani: se U[i][j] allora nella soluzione ottima
			per il problema ridotto il mazzo i e` *usato* nel vaso j. Piu`
			precisamente, se U[i][j'] (j'<j) e` il primo elemento a 1 prima di
			U[i][j] allora per tutte le soluzioni ottime con indici
			<i,j'> < <i,k> <= <i,j> il mazzo i e` inserito nel vaso k. *)

	F, V, i, j: Integer;
	ff: Text;


FUNCTION max(a,b: Integer): Integer;
BEGIN
	if a<b then max := b else max := a;
END;


BEGIN
	ASSIGN(ff, '');
	RESET(ff);

	READLN(ff, F, V);	(* Innanzitutto leggiamo i dati dentro A. *)

	FOR i:=1 TO F DO
	BEGIN
		FOR j:=1 TO V DO READ(ff, A[i][j]);
		READLN(ff);
	END;

	(* Riempiamo l'ultima riga. M[F][j] rappresenta la migliore soluzione
		ottenibile utilizzando solo l'ultimo mazzo e ponendolo a partire dal
		vaso j.  Quindi in generale il valore di M[F][j] e` il massimo tra
		il valore ottenuto mettendo l'ultimo mazzo nel posto j e il valore
		M[F][j+1]. Se il massimo e` realizzato dal primo valore registriamo
		questo fatto in U. *)

	FOR j:=V DOWNTO 1 DO
	BEGIN
		IF (j = V) OR (A[F][j] > M[F][j+1]) THEN
		BEGIN
			M[F][j] := A[F][j];
			U[F][j] := TRUE;
		END
		ELSE M[F][j] := M[F][j+1];
	END;

	(* Possiamo ora riempire le altre righe della tabella. Per calcolare
		M[i][j] massimizziamo tra la soluzione ottenuta in M[i][j+1] (cioe`
		se non utilizzassimo il vaso corrente) e la soluzione che si ottiene
		inserendo il mazzo i nel posto j e sommando la soluzione ottima per i
		rimanenti (e cioe` M[i+1][j+1]). In quest'ultimo caso registriamo nella
		matrice U l'utilizzo del vaso. *)

	FOR i:=F-1 DOWNTO 1 DO
	BEGIN
		FOR j:=V-(F-i) DOWNTO 1 DO
			(* Non ha senso utilizzare meno vasi che mazzi! *)
		BEGIN
			IF (j = V-(F-i)) OR (A[i][j]+M[i+1][j+1] > M[i][j+1]) THEN
			BEGIN
				M[i][j] := A[i][j]+M[i+1][j+1];
				U[i][j] := TRUE;
			END
			ELSE M[i][j] := M[i][j+1];
		END
	END;

	(* Alla fine, M[1][1] e` la soluzione ottima utilizzando tutti i mazzi a
		partire dal vaso 1, e quindi in posizione arbitraria. *)

	ASSIGN(ff, '');
	REWRITE(ff);

	WRITELN(ff, M[1][1]);

	(* E` anche facile, a partire da U, ricostruire la soluzione: scandiamo la
		riga corrente fino a trovare un elemento di U a 1 (il che vuol dire che
		il mazzo corrispondente alla riga corrente e` stato inserito nel vaso
		corrente), e quindi passiamo alla riga sottostante, una posizione piu`
		oltre. *)

	j := 1;
	FOR i:=1 TO F DO
		WHILE(j <= V) DO
		BEGIN
			IF U[i][j] THEN
			BEGIN
				WRITE(ff, j, ' ');
				j := j+1;
				BREAK;
			END;
			j := j+1;
		END;
END.