#include<iostream>//Multiplication Puzzle乘法之谜 zoj的第100题
using namespace std;//2008.5.8 00:10:24 Accepted 1602 C++ 00:00.01 872K 天将降大任于我
int main() //经典的dp动态规划问题
{
int a[101],f[101][101];
int n,k,min,i,j,t,m;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++) scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
{
f[i][i]=0;
f[i][i+1]=0;
f[i][i+2]=a[i]*a[i+1]*a[i+2];
}
for(k=3;k<n;k++)
{
for(i=0;i<n-k;i++)
{
min=-1;
j=i+k; //i,j表示矩阵链的两头
for(t=i+1;t<j;t++) //t从i+1开始,一步一步增加来截断矩阵
{ m=f[i][t]+f[t][j]+a[i]*a[t]*a[j]; //t为从t处截断矩阵链，公式为最优子结构的性质
if(min==-1||min>m) min=m;
}
f[i][j]=min;//f[i][j]表示矩阵链中从i到j的最小的和
}
}
printf("%d\n",f[0][n-1]);//f[0][n-1]表示从0到n－1的最小的和
}
return 0;
}
/*
((A1 x (A2 x A3)) x ((A4 x A5) x A6))
从最外层的乘号将矩阵链分成左右两边。此时，最后一次矩阵乘法需要的乘法次数已经定下来了，加上左边的
和右边的乘法次数，就得到最优(最少)乘法次数。我们可知，左边矩阵链的乘法次数也必然是最少的。如
果不是最少的，那么我们可以找到另一个加括号方法，得到更少的乘法次数，替换到解中，整个解
就可以得到一个更少的
设有n个矩阵A[1]...A[n]相乘，f[i,j]为从A[i]乘到A[j]的最少乘法次数。f[1,n]即为
所求。维数存放在数组p[0]..p[n]中。k表示将矩阵链在A[k]后断开，分成左右两部分。
当i=j时，只有一个矩阵，不需要乘法计算，所以f[i,i]=0 (i=1,2,...,n)。
当i<j时，利用最优子结构的性质，f[i,j]=min(f[i,k]+f[k+1,j]+p[i-1]*p[k]*p[j]) (i<=k<j)。
设s[i,j]表示将矩阵A[i]..A[j]相乘断开的位置，则如果k是满足上一个式子值，就有s[i,j]=k。
根据这个我们后面就可以构造出相应的最优解。
我们以矩阵链的长度为阶段，根据状态转移方程，一个一个阶段往上算。
f[i,i](i=1,2,...,n)为边界条件，不需要计算(矩阵链长度为1)；
计算f[i,i+1](i=1,2,...,n-1)(矩阵链长度为2)；
计算f[i,i+2](i=1,2,...,n-2)(矩阵链长度为3)；
……在计算f[i,j]时，只用到已计算出的f[i,k]和f[k+1,j](i<=k<j)，
可见，这样划分阶段满足无后效性。
m[i,j]给出了最优值，即计算Ai…j所需的最少数乘次数。同时还确定了计算Ai…j的最优次序中的断开位置k，也就是说，对于这个k有m[i,j] = m[i,k] + m[k+1,j] + pi-1pkpj 。若将对应于m[i,j]的断开位置k记录在s[i,j]中，则相应的最优解便可递归地构造出来。
*/
