tyvj 1198 矩阵连乘
内存限制：128 MiB
时间限制：1000 ms
标准输入输出
题目类型：传统
评测方式：文本比较
题目描述
一个nm矩阵由n行m列共nm个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个NM的矩阵乘以一个MP的矩阵等于一个NP的矩阵，运算量为nmp。 矩阵乘法满足结合律，ABC可以表示成(AB)C或者是A(BC)，两者的运算量却不同。例如当A=23 B=34 C=45时，(AB)C=64而A(BC)=90。显然第一种顺序节省运算量。 现在给出N个矩阵，并输入N+1个数，第i个矩阵是a[i-1]*a[i]

输入格式
第一行n(n<=100) 第二行n+1个数

输出格式
最优的运算量

样例
样例输入
3
2 3 4 5
样例输出
64


#include<bits/stdc++.h>
using namespace std;
long long int f[102][102],a[102];
int main()
{
	#ifndef ONLINE_JUDGE
	   freopen("linshi.in","r",stdin);
	#endif
	long long int n,i,j,k,v;
	memset(f,0x3f,sizeof(f));
	cin>>n;
	for(i=1;i<=n+1;i++)
	{
		cin>>a[i];
		f[i][i]=0;
	}
	for(i=1;i<=n;i++)
	{
		for(j=2;j<=n;j++)
		{
			v=min(i+j-1,n);
			for(k=j;k<v;k++)
			{
				f[j][v]=min(f[j][v],f[j][k]+f[k+1][v]+a[j-1]*a[k]*a[v]);
			}
		}
	}
	cout<<f[1][n];
	return 0;
}