记录编号	4259	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	ReimBurSe.	是否通过	通过
代码语言	Pascal	运行时间	0.040 s
提交时间	2008-10-15 21:38:31	内存使用	0.19 MiB

Program shizi;

Type
sc=array [0..100,0..100] of longint;
sc1=array [0..100,0..100] of longint;

Var
i,j,p,n,temp,temp1:longint;
a:sc;
s:sc1;

Begin
assign(input,'shizi.in');
assign(output,'shizi.out');
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do readln(s[i,1]);
for i:=1 to n-1 do
 s[i,2]:=s[i,1]+s[i+1,1];
i:=1;
while i<=n do begin
 a[i,1]:=s[i,1];
 i:=i+1;
end;
for i:=1 to n do begin
 for j:=1 to n-i+1 do begin
  temp:=0;
  for p:=i to i+j-1 do temp:=temp+s[p,1];
  a[i,j]:=temp;
 end;
end;
for j:=3 to n do begin
 for i:=1 to n-j+1 do begin
  s[i,j]:=s[i,j-1];
  temp:=s[i+1,j-1];
  for p:=2 to j-2 do begin
   temp1:=s[i,p]+s[i+p,j-p];
   if temp1<temp then temp:=temp1;
  end;
  if temp<s[i,j] then s[i,j]:=temp;
  s[i,j]:=s[i,j]+a[i,j];
 end;
end;
write(s[1,n]);
close(input);
close(output);
End.