Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 1 KB
program farao;
const INF = 10000;
var sz,m:array of byte;
cache:array of array of longint;
choice:array of array of byte;
A,L:byte;
procedure load;
var i,j:byte;
begin
readln(L,A);
setlength(sz,L+1);
setlength(m,L+1);
for i:=1 to L do readln(sz[i],m[i]);
setlength(cache,L+1);
setlength(choice,L+1);
for i:=0 to L do
begin
setlength(cache[i],A+1);
setlength(choice[i],A+1);
for j:=0 to A do
begin
cache[i][j]:= -1;
choice[i][j]:= 0;
end;
end;
end;
function norm(var a:longint;b:longint):boolean;
begin
result := (b<a);
if result then a:=b;
end;
function opt(L,A:byte):longint;
var sum_m,sum_v:longint;
min,res:longint;
mini,i:byte;
begin
IF CACHE[L][A]=-1 THEN
BEGIN
if (L=A) then
begin
res:=0;
end
else if A=0 then
begin
res:=INF;
end
else
begin
sum_m:=0;
sum_V:=0;
min := INF;
mini:=0;
for i:=L-1 downto A do
begin
sum_m += m[i+1];
sum_V += sz[i]*sum_m;
if norm(min , sum_V + opt(i-1,A-1)) then mini:=i;
end;
choice[L][A]:=mini;
res:=min;
end;
CACHE[L][A]:=RES;
END;
OPT:=CACHE[L][A];
end;
procedure print(L,A:byte);
begin
if A<>0 then
begin
if A=L then choice[L,A]:=L;
print(choice[L][A]-1,A-1);
writeln(choice[L][A],' ',L);
end;
end;
begin
load;
writeln(opt(L,A));
print(L,A);
end.
