记录编号	1990	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	zhai	是否通过	通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-09-10 20:21:50	内存使用	0.00 MiB

program shizi;
  type
    sz=array[1..100,0..100]of longint;
  var
    a:sz;
    n:integer;
    f1,f2:text;
    procedure ini;
      var
        i:integer;
      begin
        assign(f1,'shizi.in');reset(f1);
        assign(f2,'shizi.out');rewrite(f2);
        readln(f1,n);
        fillchar(a,sizeof(a),0);
        for i:=1 to n do readln(f1,a[1,i]);
        for i:=1 to n-1 do a[2,i]:=a[1,i]+a[1,i+1];
        close(f1);
      end;
    procedure main;
      var
        i,j,k:integer;
        b:longint;
      begin
        for i:=3 to n do begin
          for k:=1 to n-i+1 do begin
            a[i,k]:=9999999;
            b:=0;
            for j:=k to k+i-1 do inc(b,a[1,j]);
            for j:=1 to i-1 do
              if j=1 then begin
                if a[i,k]>b+a[i-j,k]  then a[i,k]:=b+a[i-j,k];
              end else if j=i-1 then begin
                if a[i,k]>b+a[j,k+1] then a[i,k]:=b+a[j,k+1];
              end else if a[i,k]>b+a[j,k]+a[i-j,k+j]
                then a[i,k]:=b+a[j,k]+a[i-j,k+j];
          end;
        end;
      end;
  begin
    ini;
    main;
    write(f2,a[n,1]);
    close(f2);
  end.