记录编号	247142	评测结果	AAAAAAAAAA
题目名称	80.石子合并	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-08 10:09:20	内存使用	0.00 MiB

#include<cstdio>
#include<cstring>
namespace cat{
	inline int cat_min(const int a,const int b){return a<b? a:b;}
	const int maxn = 100 +10;
	int f[maxn][maxn],w[maxn];//f[i][j]:把i~j合并的代价 
	int work(){
		memset(f,0x3f,sizeof(f));
		int n,x;scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			f[i][i]= 0;
			w[i]=w[i-1]+x;
		}
		for(int i=n-1;i>=1;i--)
			for(int j=i+1;j<=n;j++)
				for(int k=i;k<=j-1;k++)
					f[i][j]=cat_min(f[i][j],f[i][k]+f[k+1][j]+(w[j]-w[i-1]) );
		printf("%d",f[1][n]);
		fclose(stdin);fclose(stdout);
		return 0;
	}
}
void *a	=freopen("shizi.in","r",stdin);
void *b	=freopen("shizi.out","w",stdout);
int ans = cat::work();
int main(){;}