记录编号	12680	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.007 s
提交时间	2009-09-17 17:02:26	内存使用	0.19 MiB

program shizi;
var
  data:array [1..100] of longint;
  pre,dp:array [1..100,1..100] of longint;
  k,n,i,j:integer;
  min:longint;
begin
  fillchar (dp,sizeof(dp),0);
  fillchar (pre,sizeof(pre),0);
  assign (input,'shizi.in');
  reset (input);
  readln (n);
  for i:=1 to n do readln (data[i]);
  close (input);
  assign (output,'shizi.out');
  rewrite (output);
  for i:=1 to n do begin
    pre[i,i]:=data[i];
    for j:=i+1 to n do pre[i,j]:=pre[i,j-1]+data[j];
  end;
  for i:=2 to n do dp[i-1,i]:=data[i-1]+data[i];
  for i:=n-1 downto 1 do begin
    for j:=i+1 to n do if (dp[i,j]=0) and (i<>j) then begin
      min:=maxlongint;
      for k:=i to j-1 do if dp[i,k]+dp[k+1,j]<min then
        min:=dp[i,k]+dp[k+1,j];
      dp[i,j]:=min+pre[i,j];
    end;
  end;
  writeln (dp[1,n]);
  close (output);
end.