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

program shizi;
type
shuzu=array[1..100,1..100] of longint;
var
s,f:shuzu;
i,j,k,m,n,x,ls1,ls2:longint;
begin
assign(input,'shizi.in');reset(input);
assign(output,'shizi.out');rewrite(output);
readln(n);
for i:=1 to n do
begin
 readln(f[1,i]);
 s[1,i]:=f[1,i];
 end;
for i:=2 to n do
 for j:=1 to n-i+1 do
  begin
  for k:=j to i+j-1 do
  s[i,j]:=s[1,k]+s[i,j];
  end;
for i:=2 to n do
 for j:=1 to n-i+1 do
 begin
 x:=maxlongint;
 for k:=i-1 downto 1 do
 begin
  if k=1 then ls1:=0 else ls1:=1;
  if k=i-1 then ls2:=0 else ls2:=1;
  if x>f[k,j]*ls1+f[i-k,k+j]*ls2+s[i,j] then x:=f[k,j]*ls1+f[i-k,k+j]*ls2+s[i,j];
  end;
  f[i,j]:=x;
 end;
writeln(f[n,1]);
close(output);
end.