记录编号	35873	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2012-03-05 20:13:35	内存使用	0.27 MiB

#include<iostream>
#include<fstream>
using namespace std;
int main(){
	ifstream fin("shizi.in");
	ofstream fout("shizi.out");
	int f[101][101]={0};//f[i][j]表示j到i+j归并之耗体力最小值
	int s[101][101]={0};//s[i][j]表示i到i+j的和
	int i,j,k,n;
	fin>>n;
	for(i=0;i<n;i++){
		fin>>s[i][0];
	}//输入数据什么的......不能往f里放，因为合并一堆耗费的体力值为0
	for(i=0;i<n;i++){
		for(j=1;j<=n-1-i;j++){
			s[i][j]=s[i][j-1]+s[i+j][0];//一切可能用到的连续石子(尼玛沙子......)数之和,也算动归了
		}
	}
	for(i=1;i<n;i++){
		for(j=0;j<n-i;j++){
			for(k=0;k<i;k++){
				if(f[i][j]==0||f[k][j]+f[i-1-k][j+k+1]<f[i][j]) f[i][j]=f[k][j]+f[i-1-k][j+k+1];
				//条件转移方程自己看......因为f和s的设置方程坑爹无比......
			}
			f[i][j]+=s[j][i];
		}
	}
	fout<<f[n-1][0]<<endl;
	fin.close();
	fout.close();
	return 0;
}