记录编号	1487	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	EnAsn	是否通过	通过
代码语言	Pascal	运行时间	0.011 s
提交时间	2008-09-03 13:35:53	内存使用	0.19 MiB

program ex;
type
 ss=array[1..101,1..101]of longint;
var
 a,b:ss;
 f1,f2:text;
 i,j,n:integer;
procedure init;
 var
  i,j:integer;
 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]:=999999;
  for i:=1 to n do
   readln(f1,a[1,i]);
  for i:=1 to n do
    b[1,i]:=a[1,i];
  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];
 end;
procedure main;
 var
  i,j,k,p,q:integer;
 begin
  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 p:=0 else p:=1;
       if i-k=1 then q:=0 else q:=1;
       if a[i,j]>a[k,j]*p+a[i-k,k+j]*q+b[i,j] then
         a[i,j]:=a[k,j]*p+a[i-k,k+j]*q+b[i,j];
      end;
 end;
begin
 init;
 main;
 writeln(f2,a[n,1]);
 close(f1);
 close(f2);
end.