记录编号	24745	评测结果	AAAAAAAAAA
题目名称	石子合并	最终得分	100
用户昵称	Oo湼鞶oO	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2011-04-18 16:36:19	内存使用	0.26 MiB

#include <fstream>
#include <cstdlib>

#define I_F "shizi.in"
#define O_F "shizi.out"
#define MAXn (100+1)

using namespace std;

short n;
long s[MAXn];
long ans;

void Input();
inline long Min(long,long);
void Dynap();
void Output();

int main()
{
	Input();
	Dynap();
	Output();
	return 0;
}

void Input()
{
	int t;
	s[0]=0;
	ifstream fin(I_F);
	fin>>n;
	for (short i=1; i<=n; i++)
		fin>>t,
		s[i]=s[i-1]+t;
	fin.close();
}

inline long Min(long a, long b)
{
	return (a>b)?b:a;
}

void Dynap()
{
	long f[MAXn][MAXn];
	for (short i=0; i<=n; i++)
		for (short j=0; j<=n; j++)
			f[i][j]=LONG_MAX;
	for (short i=0; i<=n; i++)
		f[i][i]=0;
	for (short i=1; i<n; i++)
		for (short j=1; j<=n-i; j++)
		{
			for (short k=j; k<j+i; k++)
				f[j][i+j]=Min(f[j][i+j],f[j][k]+f[k+1][i+j]);
			f[j][i+j]+=(s[i+j]-s[j-1]);
		}
	ans=f[1][n];
}

void Output()
{
	ofstream fout(O_F);
	fout<<ans<<'\n';
	fout.close();
}