记录编号	1630	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	bing	是否通过	通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-09-06 14:19:48	内存使用	0.00 MiB

program bing;
var
 f1,f2:text;
 a:array[1..1000] of longint;
 b:array[1..1000,1..1000] of longint;
 n:longint;
procedure init;
var
 i:longint;
begin
 assign(f1,'shizi.in');reset(f1);
 assign(f2,'shizi.out');rewrite(f2);
 readln(f1,n);
  for i:=1 to n do readln(f1,a[i]);
 fillchar(b,sizeof(b),0);
end;
function c(x,y:longint):longint;
var
 i,t:longint;
begin
 t:=0;
 for i:=x to x+y-1 do
  t:=t+a[i];
 c:=t;
end;
procedure go;
var
 i,j,t,k:longint;
begin
 for i:=1 to n do b[i,1]:=a[i];
 for i:=1 to n-1 do b[i,2]:=a[i]+a[i+1];
 for j:=3 to n do
  for i:=1 to n-j+1 do
  begin
   t:=b[i+1,j-1];
   for k:=2 to j-1 do
   if b[i,k]+b[i+k,j-k]<=t then t:=b[i,k]+b[i+k,j-k];
   if b[i,j-1]<=t then t:=b[i,j-1];
   b[i,j]:=t+c(i,j);
  end;
end;
begin
 init;
 go;
 write(f2,b[1,n]);
 close(f1);
 close(f2);
end.