DTGAME - Tiền bạc luôn là thứ quý giá
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$R+,Q+}
{$Mode objfpc}
{$inline on}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 2011;
var
f1,f2 : text;
f,g : array[1..MAXN,1..MAXN] of longint;
s : array[0..MAXN] of longint;
n : longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
read(f1,n);
for i:=1 to n do
begin
read(f1,s[i]);
inc(s[i],s[i-1]);
end;
end;
procedure solve;
var
i,j,x,k:longint;
begin
for i:=n downto 1 do
begin
g[i,i]:=i;
for j:=i+1 to n do
begin
for k:=g[i,j-1] to g[i+1,j] do
if (i<k) then
begin
x:=min(f[i,k-1]+s[k-1]-s[i-1],f[k][j]+s[j]-s[k-1]);
if x>f[i,j] then
begin
f[i,j]:=x;
g[i,j]:=k;
end;
end;
end;
end;
writeln(f2,f[1,n]);
end;
begin
openF;
inp;
solve;
closeF;
end.