记录编号	1701	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	zpl123	是否通过	通过
代码语言	Pascal	运行时间	0.043 s
提交时间	2008-09-07 09:31:19	内存使用	0.19 MiB

program shizi;
var
a:array[1..100] of longint;
g,f:array[1..100,1..100] of longint;
i,j,min,sum,t,x,n:longint;
begin
assign(input,'shizi.in');
reset(input);
assign(output,'shizi.out');
rewrite(output);
  readln(n);
  for i:=1 to n do
    readln(a[i]);
  for i:=1 to n do
    for j:=i to n do
      begin
        sum:=0;
        for t:=i to j do
          sum:=sum+a[t];
        g[i,j]:=sum;
      end;
  for i:=1 to n do f[i,i]:=0;
  for i:=1 to n-1 do f[i,i+1]:=a[i]+a[i+1];
  for j:=2 to n do
    for i:=j-1 downto 1 do
      begin
        min:=f[i,i]+f[i+1,j];
        for x:=i+1 to j-1 do
          if min>f[i,x]+f[x+1,j] then min:=f[i,x]+f[x+1,j];
        f[i,j]:=min+g[i,j];
      end;
  writeln(f[1,n]);
close(input);
close(output);
end.