问题 E: 矩阵最优连乘问题

时间限制: 1 Sec  

内存限制: 128 MB

提交: 473  

解决: 118

[ ][ ][ ]

题目描述

已知一组连乘矩阵的各维长度，要求计算并输出计算量最小的计算顺序表达式。

输入

每行为一组连乘矩阵的各维长度，行中第一个数字是连乘矩阵的个数n，n≤100，后面是n+1个维长。 矩阵个数为0表示输入结束。

输出

对每行输入，计算最优计算顺序，并以括号形式将计算表达式输出，各矩阵用A0, A1, ..的形式表示。

样例输入

1 10 202 10 20 303 10 20 30 406 30 35 15 5 10 20 250

样例输出

A0A0A1(A0A1)A2(A0(A1A2))((A3A4)A5)

动态规划经典问题。由于矩阵的乘法满足结合律，故计算矩阵的连乘积可以有不同的计算次序。

矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p*q的矩阵，B是一个q*r的

矩阵，其乘机C=AB是一个p*r的矩阵，总共需要pqr次数乘。

假如有3个矩阵的尺寸分别为10*100，100*5和5*50。若以(A0A1)A2这种方式计算，3个矩

阵的连乘积需要的数乘次数为7500。若以A0(A1A2)这种方式计算，所需的数乘次数为75000

。显然，在即算矩阵连乘积时，加括号方式对计算量有很大影响。

 

我们假设m[i][j]为 计算子成绩的代价 A i..k 和 A k+1..j 的代价，再加上这两个矩阵相乘的代价

的最小值。

 

即 m[i][j]=  min(m[i][[k]+m[k+1][j]+p[i-1]p[k]p[j])  当然这是i！=j的情况。 如果i=j 意味着

只有一个矩阵自然就没什么可以分的了。 所以 m[i][j]=0

 

即   m[i][j]=     min(m[i][k]+m[k+1][j]+p[i-1]p[k]p[j])   i<j

                      0                                                      i=j

 

大家注意到了问题中最优解包含着其子问题的最优解，这就是动态规划求解的显著特征啦！

 

另外我们在动态规划的过程中用 s[i][j] 数组记录 m[i][j]断开的位置 k，后面即可通过动态

规划构造出相应的最优解。

 

 

下附上代码

 

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAX=1010;int p[MAX],m[MAX][MAX],s[MAX][MAX];int n;void MATRIX_CHAIN_ORDER(){    for(int i=0;i<=n;i++)    {        m[i][i]=0;    }    for(int l=2;l<=n;l++)//矩阵链表长度        for(int i=1;i<=n-l+1;i++)        {            int j=i+l-1;            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];            s[i][j]=i;            for(int k=i+1;k
          
           >n&&n)    {        for(int i=0;i<=n;i++)        {            cin>>p[i];        }        MATRIX_CHAIN_ORDER();        PRINT_OPTIMAL_PARENS(1,n,1);        cout<