Letöltés: fg_fazekasr.dpr {$A+,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S-,T-,U-,V+,W-,X+,Y+,Z1} {$MINSTACKSIZE $00004000} {$MAXSTACKSIZE $00100000} {$IMAGEBASE $00400000} {$APPTYPE CONSOLE} PROGRAM fazekasr; CONST ch = '8'; inputFile = 'FAZEKAS'+ch+'.BE'; outputFile = 'FAZEKAS'+ch+'.KIX'; maxn = 10000; VAR N, K: INTEGER; {az egetesi idok listaja:} list: ARRAY [1..maxn] OF RECORD E: BYTE; END; cache: ARRAY [1..maxn+1] OF INTEGER; choice: ARRAY [1..maxn] OF BYTE; PROCEDURE Load; VAR T: Text; i: INTEGER; BEGIN Assign(T, inputFile); Reset(T); ReadLn(T, N, K); FOR i:= 1 TO N DO BEGIN ReadLn(T, list[i].e); END; Close(T); END; {Load} {megadja az elso_targy, ..., N indexu targy-sorozat legjobb egetesi idejet} FUNCTION Best(elso_targy: INTEGER): INTEGER; VAR i: INTEGER; max: INTEGER; {az aktualisan berakott targyak e. ideje} ido: INTEGER; {max + a maradek targyak e. ideje} tmp: INTEGER; BEGIN IF elso_targy > N THEN cache[elso_targy]:= 0; IF cache[elso_targy] = -1 THEN BEGIN {ha meg nincs tarolt ertek} max:= 0; {tmp a legnagyobb indexu targy, amit meg az elso_targy-al berakhatunk a kemencebe:} tmp:= elso_targy+K-1; IF tmp > N THEN tmp:= N; {vegigprobalgatjuk, hogy mennyi lesz az egetesi ido, ha 1, 2, ..., i-elso_targy+1 targyat teszunk a kemencebe} FOR i:= elso_targy TO tmp DO BEGIN {a bekerulo targyak egetesi ideje, az egyedi egetesi idok maximuma...:} IF list[i].e > max THEN max:= list[i].e; {a teljes egetesi ido ennyi berakott targy eseten} ido:= max + Best(i+1); {ha jobb idot talaltunk a legutobbinal, vagy nem volt legutobbi:} IF (cache[elso_targy] = -1) OR (ido < cache[elso_targy]) THEN BEGIN cache[elso_targy]:= ido; choice[elso_targy]:= i-elso_targy+1; END; END; END; Best:= cache[elso_targy]; END; {Best} PROCEDURE Process; VAR T: Text; i: INTEGER; BEGIN Assign(T, outputFile); Rewrite(T); FOR i:= 1 TO N DO cache[i]:= -1; WriteLn(T, Best(1)); {eloallitjuk az optimalis targy-sorozatot:} i:= 1; WHILE i <= N DO BEGIN WriteLn(T, i, ' ', i+choice[i]-1); i:= i+choice[i]; END; Close(T); END; {Process} BEGIN Load; Process; END. |