NBUT 1003 最优矩阵链乘

た入场券 2021-12-18 13:49 218阅读 0赞

## 题意：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。 ##

## 思路：如果最后一次乘法是第k个，则从A1,A2,....Ak和Ak+1,Ak+2......An两个子序列都是最优乘法了，所以我们只需保证两个子结构最优，而子结构也是可以这样划分的，所以我们每次考虑的问题就是，把Ai,Ai+1...Aj乘起来的最少乘法次数，用dp\[i\]\[j\]表示这个问题的值，有dp\[i\]\[j\]=min\{dp\[i\]\[k\]+dp\[k+1\]\[j\]+pi-1\*pk\*pj\}，按照j-i递增的方向递推，因为长区间的值依赖于短区间的值。 ##

## 参考：[https://blog.csdn.net/Q755100802/article/details/82949499][https_blog.csdn.net_Q755100802_article_details_82949499]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    const int maxn=210;
    const int INF=0x3f3f3f3f;
    ll dp[maxn][maxn];
    ll p[maxn];
    
    int main()
    {
        ll n;
        while(scanf("%lld",&n)!=EOF)
        {
            for(int i=0;i<n+1;i++)
            {
                scanf("%lld",&p[i]);
            }
            //长度为1的矩阵集合，都归0，没有乘法计算。
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(i==j)
                        dp[i][j]==0;
                }
            }
            for(int x=2;x<=n;x++)//矩阵集合的长度，2,3....n
            {
                for(int i=1;i<=n-x+1;i++)
                {
                    //按照j-i递增的顺序递推，因为j是矩阵集合的右端，而长区间的值依赖于短区间
                    int j=x+i-1;
                    dp[i][j]=INF;
                    for(int k=i;k<j;k++)
                    {
                        dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]);
                    }
                }
            }
            printf("%lld\n",dp[1][n]);
        }
        return 0;
    }

[https_blog.csdn.net_Q755100802_article_details_82949499]: https://blog.csdn.net/Q755100802/article/details/82949499