记录编号	286213	评测结果	AAAAA
题目名称	最优矩阵链乘	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-07-29 22:16:58	内存使用	0.34 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
int n,a[maxn],f[maxn][maxn]={{0}};
int main(){
#define MINE
#ifdef MINE
	freopen("goodmatrix.in","r",stdin);
	freopen("goodmatrix.out","w",stdout);
#endif
	scanf("%d",&n);
	n++;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	n--;
	for(int i=1;i<=n;i++)f[i][i+1]=a[i]*a[i+1]*a[i+2];
	for(int d=3;d<=n;d++)for(int i=1,j;i+d-1<=n;i++){
		j=i+d-1;
		f[i][j]=0x7fffffff;
		for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+a[i]*a[k+1]*a[j+1]);
		//谁来告诉我这堆+1是干嘛的
	}
	printf("%d",f[1][n]);
	return 0;
}