记录编号	91998	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-03-17 21:47:17	内存使用	0.36 MiB

#include <fstream>
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 0x7FFFFFFF;
int cost[105][105]={0}, sum[105]={0}, N;//cost[a,b)表示第a到第b-1堆的状态

int main()
{
	freopen("shizi.in","r",stdin);
	freopen("shizi.out","w",stdout);
	cin >> N;
	
	int i,j,k;
	for(i=1;i<=N;i++) //READIN
	{
		cin >> k;
		sum[i]=sum[i-1]+k;
	}
	
	for(i=2;i<=N;i++)    //i为当前考虑堆数
		for(j=1;j<=N+1-i;j++)    //考虑[j,j+i)区间的状态
		{
			int min = MAX;
			int C = sum[j+i-1]-sum[j-1];
			for(k=j+1;k<j+i;k++)   //查找cost[i,j+1)的最小值
				if(min > (cost[j][k]+cost[k][j+i]))min = (cost[j][k]+cost[k][j+i]);
			cost[j][j+i] = C + min;
		}
	
	cout << cost[1][N+1];
	return 0;
}