比赛 20101025 评测结果 AWWWWWWWWW
题目名称 整理书本 最终得分 10
用户昵称 make 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-10-25 19:00:43
显示代码纯文本
program book;
var
  v,w:array [1..400] of longint;
  h:array [1..400,1..400] of record
                             data,v,w:longint;
                             end;
  n,i,j:longint;
  f1,f2:text;

procedure init;
var i,j:longint;
begin
 assign(f1,'book.in'); reset(f1);
 assign(f2,'book.out'); rewrite(f2);
 readln(f1,n);
 for i:=1 to n do
  readln(f1,w[i],v[i]);
 close(f1);
 for i:=1 to n-1 do begin
  h[i,i+1].data:=w[i]-v[i]+w[i+1]-v[i+1];
  h[i,i+1].w:=w[i]+w[i+1];
  h[i,i+1].v:=v[i]+v[i+1];
 end;
end;

procedure min(x,y:longint);
var i:longint;
begin
 if (h[x,y-1].w-h[x,y-1].v)+(w[y]-v[y])+h[x,y-1].data<(h[x+1,y].w-h[x+1,y].v)+(w[x]-v[x])+h[x+1,y].data then
 begin
  h[x,y].data:=(h[x,y-1].w-h[x,y-1].v)+(w[y]-v[y])+h[x,y-1].data;
  h[x,y].w:=h[x,y-1].w+w[y];
  h[x,y].v:=h[x,y-1].v+v[y];
 end else begin
  h[x,y].data:=(h[x+1,y].w-h[x+1,y].v)+(w[x]-v[x])+h[x+1,y].data;
  h[x,y].w:=h[x+1,y].w+w[x];
  h[x,y].v:=h[x+1,y].v+v[x];
 end;
 for i:=x+1 to y-2 do
  if (h[x,i].w-h[x,i].v)+(h[i+1,y].w-h[i+1,y].v)+h[x,i].data+h[i+1,y].data<h[x,y].data then begin
   h[x,y].data:=(h[x,i].w-h[x,i].v)+(h[i+1,y].w-h[i+1,y].v)+h[x,i].data+h[i+1,y].data;
   h[x,y].w:=h[x,i].w+h[i+1,y].w;
   h[x,y].v:=h[x,i].v+h[i+1,y].v;
  end;
end;

procedure play;
var i,k:longint;
begin
 k:=2;
 i:=1;
 while k<=n-1 do begin
  while i+k<=n do begin
   min(i,i+k);
   i:=i+1;
  end;
  k:=k+1;
 end;
end;


begin
 init;
 play;
 writeln(f2,h[1,n].data);
 close(f2);
end.