DTGAME - Tiền bạc luôn là thứ quý giá
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=2000;
var n:longint;
a:array[0..maxn] of longint;
f,k:array[1..maxn,1..maxn] of longint;
procedure rf;
var i,t:longint;
begin
assign(input,fi);
reset(input);
readln(n);
a[0]:=0;
for i:=1 to n do
begin
readln(t);
a[i]:=a[i-1]+t;
end;
close(input);
end;
function min(x,y:longint):longint;
begin
if x>y then min:=y else min:=x;
end;
procedure pr;
var i,j,l,t,u:longint;
begin
for i:=1 to n do k[i,i]:=i;
for l:=2 to n do
for i:=1 to n-l+1 do
begin
j:=i+l-1;
for t:=k[i,j-1] to k[i+1,j] do
begin
if t=i then continue;
u:=min(f[i,t-1]+a[t-1]-a[i-1],f[t,j]+a[j]-a[t-1]);
if u>f[i,j] then
begin
f[i,j]:=u;
k[i,j]:=t;
end;
end;
end;
end;
procedure wf;
begin
assign(output,fo);
rewrite(output);
write(f[1,n]);
close(output);
end;
begin
rf;
pr;
wf;
end.