记录编号	164518	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-06-02 08:22:06	内存使用	0.37 MiB

#include <cstdio>

using namespace std;

int n;
int stone[101];
int sum[101][101];
int f[101][101];

inline int min(int a,int b) {
	return a < b ? a : b;
}

inline int in() {
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')c=getchar();
	for(; c>='0'&&c<='9'; c=getchar())x=x*10+c-'0';
	return x;
}

int main() {
	freopen("shizi.in","r",stdin);
    freopen("shizi.out","w",stdout);
	int i,j,len,k;
	n=in();
	for(i=1; i<=n; ++i)
		stone[i]=in();
	for(i=1; i<=n; ++i) {
		f[i][i]=0;
		sum[i][i]=stone[i];
		for(j=i+1; j<=n; ++j)
			sum[i][j]=sum[i][j-1]+stone[j];
	}
	for(len=2; len<=n; ++len)
		for(i=1; i<=n-len+1; i++) {
			j=i+len-1;
			f[i][j]=0x3fffffff;
			for(k=i; k<=j-1; k++)
				f[i][j]=min(f[i][k]+f[k+1][j]+sum[i][j],f[i][j]);
		}
	printf("%d",f[1][n]);
}