记录编号	185290	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2015-09-05 18:08:30	内存使用	0.41 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=0x7fffffff;
int N,s[110][110]={0},m[110][110]={0},w[110][110]={0};
int DP(int i,int j)
{
	if(i==j)
	{
		s[i][j]=j;
		m[i][j]=0;
		return m[i][j];
	}
	if(i+1==j)
	{
		s[i][j]=j;
		m[i][j]=w[i][j];
		return m[i][j];
	}
	if(m[i][j]) return m[i][j];
	m[i][j]=maxn;
	DP(i,j-1);DP(i+1,j);
	for(int k=s[i][j-1];k<=s[i+1][j];k++)
	{
		int tem=DP(i,k-1),tem2=DP(k,j);
		if(tem+tem2<m[i][j])
		{
			m[i][j]=tem+tem2;
			s[i][j]=k;
		}
	}
	m[i][j]+=w[i][j];
	return m[i][j];
}
int main()
{
	freopen("shizi.in","r",stdin);
	freopen("shizi.out","w",stdout);
	scanf("%d",&N);
	int a;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&a);
		for(int j=1;j<=i;j++)
			w[j][i]=w[j][i-1]+a;
	}
	int ans=DP(1,N);
	//cout<<m[2][3]<<endl;
	printf("%d\n",ans);
	return 0;
}