Optimal Array Multiplication Sequence UVA - 348（矩阵连乘问题，区间dp+记录路径）

71 阅读 0 评论 47 点赞

我是靠谱客的博主无心纸飞机，最近开发中收集的这篇文章主要介绍Optimal Array Multiplication Sequence UVA - 348（矩阵连乘问题，区间dp+记录路径），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：要求乘的次数最小，分析子最优子结构：任意一个区间的最小乘次数，取决于先乘那几个（等价于最后乘那两个），所以思路就是去枚举最后乘的那个就行。

状态转移方程：dp[i][j]=min(dp[i][k]+dp[k+1][j]+a[i]*b[k]*b[j]) k>=i&&k<j;

难点在于如何输出路径：

可以在计算最小值的时候，记录枚举出的最小的k，也就是说dp[i][j]=min(dp[i][k]+dp[k+1][j]+a[i]*b[k]*b[j]) k>=i&&k<j取最小值时候的k值，记录下来就行。path[i][j]=k;

输出的时候，只要当遇见path[i][j]=k时，输出x就行。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+7;
const int inf=0x3f3f3f3f;
typedef long long ll;
int a[maxn],b[maxn];
int dp[maxn][maxn];
int path[maxn][maxn];
int n;
int dfs(int i,int j)
{
    int &ans=dp[i][j];
    if(ans<inf) return ans;
    if(i==j) return ans=0;
    for(int k=i;k<j;k++)
    {
        int tmp=dfs(i,k)+dfs(k+1,j)+a[i]*b[k]*b[j];
        if(tmp<ans)
        {
            ans=tmp;
            path[i][j]=k;
        }
    }
    return ans;
}
void print(int i,int j)
{
    if(i==j)
    {
        printf("A%d",i);
        return;
    }
    printf("(");
    for(int k=i;k<j;k++)
    {
        if(path[i][j]==k)
        {
            print(i,k);
            printf(" x ");
            print(k+1,j);
            break;
        }
    }
    printf(")");
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int Case=0;
    while(scanf("%d",&n)!=EOF&&n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i],&b[i]);
        }
        memset(dp,inf,sizeof(dp));
        memset(path,0,sizeof(path));
        dp[1][n]=dfs(1,n);
        printf("Case %d: ",++Case);
        print(1,n);
        printf("n");
    }
    return 0;
}