CATGO - Cắt gỗ
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
PROGRAM CATGO;
CONST
FINP='';
FOUT='';
max=52;
VAR
t,n,m:integer;
gt:array[0..max] of longint;
c:array[1..max] of longint;
d:array[1..max,0..max*max] of longint;
kq:array[0..max,0..max*max] of longint;
procedure readInput;
var
f:text;
u,i:integer;
begin
assign(f,FINP); reset(f);
read(f,n);
for i:=1 to n do
read(f,c[i]);
read(f,m);
for i:=1 to m do
begin
read(f,u,gt[u]);
d[u,0]:=gt[u];
end;
close(f);
end;
function max2(a,b:longint):longint;
begin
if a>b then max2:=a else max2:=b;
end;
procedure writeOutput;
var
f:text;
answer,i:longint;
begin
assign(f,FOUT); rewrite(f);
answer:=0;
for i:=0 to t do
answer:=max2(answer,kq[n,i]);
writeln(f,answer);
close(f);
end;
procedure QHD1;
var
i,j,k:integer;
begin
for i:=1 to max do
for j:=1 to i-1 do
for k:=1 to i-1 do
d[i,j]:=max2(d[i,j],d[k,j-1]+gt[i-k]);
end;
function min2(a,b:longint):longint;
begin
if a<b then min2:=a else min2:=b;
end;
procedure QHD2;
var
i,j,k,u,g,l,gg:integer;
begin
t:=0;
for i:=1 to n do
begin
u:=c[i]; l:=t; t:=t+u-1;
gg:=min2(t,max);
for j:=0 to gg do
begin
g:=min2(l,j);
g:=min2(max,g);
for k:=0 to g do
kq[i,j]:=max2(kq[i,j],kq[i-1,k]+d[u,j-k]+k*(k+1) div 2-j*(j+1) div 2);
end;
end;
end;
BEGIN
readInput;
QHD1;
QHD2;
writeOutput;
END.