记录编号	70120	评测结果	AAAAA
题目名称	最优矩阵链乘	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-09-24 12:47:40	内存使用	0.46 MiB

#include<fstream>
using namespace std;
ifstream fin("goodmatrix.in");
ofstream fout("goodmatrix.out");
int f[200][200];
int a[200],n;
const int INF=999999999;
int main()
{
	fin>>n;
	int i,j,k,l;
	int P;
	for(i=0;i<=n;i++)
	{
		fin>>a[i];
		f[i][i]=0;
	}
	for(l=2;l<=n;l++)//外层枚举长度
	{
		P=n-l+1;//计算最后的点的可能位置
		for(i=1;i<=P;i++)
		{
			j=i+l-1;//计算长度为l起始点为i的末尾点
			f[i][j]=INF;
			for(k=i;k<j;k++)//开始动规
			{
				if(f[i][k]+f[k+1][j]+a[i-1]*a[j]*a[k]<f[i][j])
					f[i][j]=f[i][k]+f[k+1][j]+a[i-1]*a[j]*a[k];
			}
		}
	}
	fout<<f[1][n]<<endl;
	return 0;
}