记录编号	147134	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-01-24 21:57:36	内存使用	0.33 MiB

#include <cstdio>
#include <algorithm>
#define INF 10000000
using namespace std;

int n,sum[105],v[105][105]; 

int f(int i,int j){
	if(v[i][j]) return v[i][j];
	if(i==j) return 0;
	if(i+1==j) return v[i][j]=sum[j]-sum[i-1];
	v[i][j]=INF;
	for(int k=i;k<=j;k++)
	 v[i][j]=min(v[i][j],f(i,k)+f(k+1,j)+sum[j]-sum[i-1]);
	return v[i][j]; 
}

int main()
{
	freopen("shizi.in","r",stdin);
	freopen("shizi.out","w",stdout);
	
	scanf("%d",&n);
	for(int k=1;k<=n;k++){
		scanf("%d",&sum[k]);
		sum[k]+=sum[k-1];
	}
	
	printf("%d",f(1,n));
	return 0;
}

/*
60
493
169
688
111
252
882
791
69
74
177
282
56
994
288
387
257
967
907
873
755
392
719
385
651
916
379
36
450
519
863
851
733
105
369
944
447
87
174
506
320
702
137
996
235
29
757
127
583
966
963
500
910
630
59
19
386
919
494
419
918
170524
*/