比赛 20101025 评测结果 AAAAAAAAAA
题目名称 整理书本 最终得分 100
用户昵称 Achilles 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-10-25 20:57:42
显示代码纯文本
program book;
var
  i,j,k,n:longint;
  sz:array[0..400,1..2]of longint;
  tab:array[0..400,0..400,1..3]of longint;
begin
  assign(input,'book.in');
  assign(output,'book.out');
  reset(input);
  rewrite(output);
  readln(n);
  for i:=1 to n do
    readln(sz[i,1],sz[i,2]);
  for i:=1 to n do
    for j:=1 to n do
      tab[i,j,3]:=2000000000;
  for i:=1 to n do
  begin
    tab[i,i,3]:=0;
    tab[i,i,1]:=sz[i,1];
    tab[i,i,2]:=sz[i,2];
  end;
  for i:=2 to n do
    for j:=1 to n-i+1 do
    begin
      tab[j,j+i-1,1]:=tab[j,j+i-2,1]+tab[j+i-1,j+i-1,1];
      tab[j,j+i-1,2]:=tab[j,j+i-2,2]+tab[j+i-1,j+i-1,2];
      for k:=j to j+i-2 do
        if tab[j,k,1]+tab[k+1,j+i-1,1]+tab[j,k,3]+tab[k+1,j+i-1,3]-tab[j,k,2]-tab[k+1,j+i-1,2]<tab[j,j+i-1,3] then
          tab[j,j+i-1,3]:=tab[j,k,1]+tab[k+1,j+i-1,1]+tab[j,k,3]+tab[k+1,j+i-1,3]-tab[j,k,2]-tab[k+1,j+i-1,2];
    end;
  writeln(tab[1,n,3]);
  close(input);
  close(output);
end.