记录编号	2140	评测结果	AAWWWWWWWW
题目名称	石子合并	最终得分	20
用户昵称	书剑飘零	是否通过	未通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-09-13 20:10:31	内存使用	0.00 MiB

program spk_szgb; 
  var 
    f:array[0..200,0..200] of integer; 
    k,i,j,n,min,p,t,pp:integer; 
    a:array[1..200] of integer; 
    f1,f2:text;
begin 
  assign(f1,'shizi.in');
  assign(f2,'shizi.out');
  reset(f1);rewrite(f2);
  
  readln(f1,n); 
  for i:=1 to n do read(f1,a[i]); 
  fillchar(f,sizeof(f),0); 
  for j:=2 to n do 
    for i:=1 to n do 
      begin 
        t:=0; 
        min:=3000; 
        for p:=i to i+j-1 do 
          begin 
            if p>n then t:=t+a[p mod n] else t:=t+a[p]; 
          end; 
        for k:=1 to j-1 do 
          begin 
            if i+k>n then pp:=i+k-n else pp:=i+k; 
            if min>f[i,k]+f[pp,j-k] then min:=f[i,k]+f[pp,j-k]; 
          end; 
        f[i,j]:=min+t; 
      end; 
  min:=f[1,n]; 
  for i:=1 to n do if f[i,n]<min then min:=f[i,n]; 
  writeln(f2,min);
  close(f1);
  close(f2); 
end.