一个n*m矩阵由n行m列共n*m个数排列而成。两个矩阵A和B可以相乘当且仅当A的列数等于B的行数。一个N*M的矩阵乘以一个M*P的矩阵等于一个N*P的矩阵，运算量为nmp。
   矩阵乘法满足结合律，A*B*C可以表示成(A*B)*C或者是A*(B*C)，两者的运算量却不同。例如当A=2*3 B=3*4 C=4*5时，(A*B)*C=64而A*(B*C)=90。显然第一种顺序节省运算量。
   现在给出N个矩阵，并输入N+1个数，第i个矩阵是a[i-1]*a[i]

第一行n(n<=100)
第二行n+1个数

最优的运算量

输入

3 
2 3 4 5

输出

64

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const long long maxn = ,maxint = 98765432123456L;

long long n,a[maxn],f[maxn][maxn];

int main(){

    cin>>n;

    for(int i = ;i <= n+;i++){

        cin>>a[i];

    }

    for(int i = ;i <= n+;i++){

        for(int j = ;j <= n+;j++){

            f[i][j] = maxint;

        }

    }

    long long j,tmp;

    for(int l = ;l <= n+;l++){

        for(int i = ;i <= n-;i++){

            j = i + l - ;

            for(int k = i + ;k <= j-;k++){

                tmp = a[i] * a[k] * a[j];

                if(k - i >= ) tmp += f[i][k];

                if(j - k >= ) tmp += f[k][j];

                f[i][j] = min(f[i][j],tmp);

            }

        }

    }

    cout<<f[][n+];

    return ;

}