比赛 |
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.