ZOJ 1276 DP

给出一系列的1x2的矩阵，要你求出矩阵以什么样的次序相乘才使得相乘次数最少，。（不用排序，只要决定该矩阵是和前面相乘比较好，还是后面）。

今天仔细想了一下，跟之前做的DP题目做了下对比，你比如说猴子堆砖块拿香蕉那题，那种是通过设定局部量j,求得1到j的局部最优解，再递增j，直到求得全局最优解

这种题目，由于两两之间不同的顺序就能产生不同解，所以，是通过设定局部量j，求得相隔为j的两矩阵相乘的最优解，再递增j，直到全局。

一开始我的思路就局限在第一种，所以怎么想也没理清怎么写。

还有，这个题目输出比较麻烦，在DP过程中，用一个二维数组记录求得i到j之间最优解的时候，是哪个矩阵在前面。

通过递归的方式输出，好厉害，膜拜浙西贫农大神。

#include <iostream>

#include <cstdio>

using namespace std;

int dp[][];

int a[],b[];

int rec[][];

void print(int i,int j)

{

    if (i==j){

        cout<<"A"<<i;

        return;

    }

    if (i<j){

        cout<<"(";

        print(i,rec[i][j]);

        cout<<" x ";

        print(rec[i][j]+,j);

        cout<<")";

    }

}

int main()

{

    int n;

    int cases=;

    while (scanf("%d",&n)&&n){

        int i,j,k;

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

            scanf("%d %d",&a[i],&b[i]);

        }

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

            for (k=;k<=n;k++){

            if (j==k) dp[j][k]=;

            else

                dp[j][k]=<<;

            rec[j][k]=j;

            }

        }

        int p;

        for (p=;p<=n-;p++){

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

                j=p+i;

                int temp;

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

                    temp=dp[i][k]+dp[k+][j]+a[i]*b[k]*b[j];

                    if (temp<dp[i][j]){

                    dp[i][j]=temp;

                    rec[i][j]=k;

                   // cout<<"rec "<<i<<" "<<j<<" "<<k<<" "<<temp<<endl;

                }

              }

            }

        }

        cout<<"Case "<<cases<<": ";

        cases++;

        print(,n);

        putchar('\n');

    }

    return ;

}

巴特西

ZOJ 1276 DP

最新文章

热门文章