ZOJ 1276 DP

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

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

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

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

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

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

#include <iostream>
#include <cstdio>
using namespace std;
int dp[15][15];
int a[15],b[15];
int rec[15][15];
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]+1,j);
        cout<<")";
    }
}
int main()
{
    int n;
    int cases=1;
    while (scanf("%d",&n)&&n){
        int i,j,k;
        for (i=1;i<=n;i++){
            scanf("%d %d",&a[i],&b[i]);
        }
        for (j=1;j<=n;j++){
            for (k=1;k<=n;k++){
            if (j==k) dp[j][k]=0;
            else
                dp[j][k]=1<<30;
            rec[j][k]=j;
            }
        }
        int p;
        for (p=1;p<=n-1;p++){
            for (i=1;i<=n-p;i++){
                j=p+i;
                int temp;
                for (k=i;k<=j-1;k++){
                    temp=dp[i][k]+dp[k+1][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(1,n);
        putchar('
');
    }
    return 0;
}