记录编号	247184	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2016-04-08 10:32:01	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define sum(i,j) (b[j]-b[i-1])
using namespace std;
int f[110][110],b[110],n,a[110],temp;
int main(){
#define COGS
#ifdef COGS
	freopen("shizi.in","r",stdin);
	freopen("shizi.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]+b[i-1],f[i][i]=0;
	for(int d=2;d<=n;d++){
		for(int i=1;i<=n-d+1;i++){
			int j=i+d-1;
			temp=0x7fffffff;
			for(int k=i;k<j;k++)temp=min(temp,f[i][k]+f[k+1][j]);
			f[i][j]=temp+sum(i,j);
		}
	}
	printf("%d\n",f[1][n]);
	return 0;
}