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.

Download