记录编号	3634	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	王瑞祥K	是否通过	通过
代码语言	Pascal	运行时间	0.010 s
提交时间	2008-10-08 20:03:47	内存使用	0.15 MiB

program shizi(input,output);
var
 a:array[1..100,1..100]of longint;
 n:integer;
procedure ini;
var i:integer;
begin
 assign(input,'shizi.in');
 assign(output,'shizi.out');
 reset(input);rewrite(output);
 readln(input,n);
 fillchar(a,sizeof(a),0);
 for i:=1 to n do readln(input,a[1,i]);
 for i:=1 to n-1 do a[2,i]:=a[1,i]+a[1,i+1];
end;
procedure main;
var i,j,k:integer; s:longint;
begin
 for i:=3 to n do begin
  for k:=1 to n-i+1 do begin
   a[i,k]:=999999999;
   s:=0;
   for j:=k to k+i-1 do inc(s,a[1,j]);
   for j:=1 to i-1  do
    if j=1 then begin
     if a[i,k]>s+a[i-j,k] then a[i,k]:=s+a[i-j,k];end
    else if j=i-1 then begin
     if a[i,k]>s+a[j,k+1] then a[i,k]:=s+a[j,k+1];end
     else if a[i,k]>s+a[j,k]+a[i-j,k+j] then a[i,k]:=s+a[j,k]+a[i-j,k+j];
  end;
 end;
end;
begin
 ini;
 main;
 write(output,a[n,1]);
 close(input);close(output);
end.