记录编号	1537	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	打不死的羊	是否通过	通过
代码语言	Pascal	运行时间	0.010 s
提交时间	2008-09-03 20:51:23	内存使用	0.19 MiB

program shizi;
Type
fxz=array[1..100,1..100] of longint;
const
max=99999999;
Var
f1,f2:text;
a,b:fxz;
m,k,i,j,q,min,n,x,y:longint;
begin
assign(f1,'shizi.in');
assign(f2,'shizi.out');
reset(f1);rewrite(f2);
readln(f1,n);
for i:=1 to n do
for j:=1 to n+1-i do
a[i,j]:=max;
for i:=1 to n do
begin
readln(f1,a[1,i]);
b[1,i]:=a[1,i];
end;
for i:=2 to n do
for j:=1 to n+1-i do
b[i,j]:=b[i-1,j]+b[1,j+i-1];
for i:=2 to n do
 for j:=1 to n+1-i do
 for k:=i-1 downto 1 do
 begin
  if k=1 then x:=0 else x:=1;
  if i-k=1 then y:=0 else y:=1;
  if a[i,j]>b[i,j]+a[k,j]*x+a[i-k,j+k]*y then a[i,j]:=b[i,j]+a[k,j]*x+a[i-k,j+k]*y;
 end;
writeln(f2,a[n,1]);
close(f1);close(f2);
end.