记录编号	201358	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	VacaTionGOD	是否通过	通过
代码语言	Pascal	运行时间	0.017 s
提交时间	2015-10-30 17:26:39	内存使用	0.24 MiB

var
 a:array[0..1000]of longint;
 f,s:array[0..100,0..100]of longint;
 i,j,m,n,k:longint;
function sum(x,y:longint):longint;
 var su,i:longint;
 begin
  su:=0;
  for i:=x to y do
   su:=su+a[i];
  sum:=su;
end;
begin
assign(input,'shizi.in');
reset(input);
assign(output,'shizi.out');
rewrite(output);
 readln(n);
 for i:=1 to n do
  readln(a[i]);
 for i:=1 to n do
   for j:=1 to n do
     s[i,j]:=sum(i,j);

 for i:=1 to n do
  for j:=1 to n do
   if i=j then f[i,j]:=0
   else f[i,j]:=maxlongint div 2;

 for i:=1 to n do
  for j:=1 to n-i do
   for k:=j to i+j-1 do
    if  f[j,i+j]>f[j,k]+f[k+1,i+j]+s[j,k]+s[k+1,j+i] then
      f[j,i+j]:=f[j,k]+f[k+1,i+j]+s[j,k]+s[k+1,j+i];
    writeln(f[1,n]);
close(input);
close(output);
end.