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

program shizi(f1,f2);
var
  s:array[0..101,0..101] of longint;
  x,y,i,j,n,m,k,min:longint;
  f1,f2:text;
begin
  assign(f1,'shizi.in');
  assign(f2,'shizi.out');
  reset(f1); rewrite(f2);
  readln(f1,n);
  for i:=1 to n do readln(f1,s[1,i]);
  for i:=1 to n-1 do s[2,i]:=s[1,i]+s[1,i+1];
  for j:=3 to n do begin
    for i:=1 to (n-j+1) do begin
       m:=0;
       for k:=i to (i+j-1) do m:=m+s[1,k];
       min:=s[j-1,i];
       if s[j-1,i+1]<=min then min:=s[j-1,i+1];
       if j>3 then begin
         for k:=2 to j-2 do  begin
           if min>=s[k,i]+s[j-k,i+k]
           then min:=s[k,i]+s[j-k,i+k]
         end;
       end;
       s[j,i]:=min+m;
     end;
  end;
  writeln(f2,s[n,1]);
  close(f1);  close(f2);
end.