记录编号	5090	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	elysian	是否通过	通过
代码语言	Pascal	运行时间	0.008 s
提交时间	2008-10-24 20:00:06	内存使用	0.19 MiB

program cc;
const
fin='shizi.in';fout='shizi.out';
var
g:array[1..100,1..100] of longint;
a:array[1..100] of longint;
f:array[1..100,1..100] of longint;
n,s,i,j,k,min:longint;
f1,f2:text;

procedure init;
begin
assign(f1,fin);reset(f1);
reset(f1);
readln(f1,n);
for i:=1 to n do
read(f1,a[i]);
close(f1);

for i:=1 to n do
begin
g[i,i]:=a[i];
for j:=i+1 to n do
begin
g[i,j]:=g[i,j-1]+a[j];
g[j,i]:=g[i,j];
end;


end;

end;

procedure main;
var
i,j,k:longint;
min:longint;
begin
min:=maxlongint;
for i:=2 to n do
for j:=1 to n-i+1 do
begin
min:=f[i-1,j];
for k:=1 to i-2 do
if f[k,j]+f[i-k,j+k]<min then min:=f[k,j]+f[i-k,j+k];
f[i,j]:=g[j,i+j-1] +min;
end;

end;


begin
init;
main;
assign(f2,fout);rewrite(f2);
writeln(f2,f[n,1]);
close(f2);
end.