UVAoj 348 - Optimal Array Multiplication Sequence

/*
    题意：矩阵相乘的最少的步数
    dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j]);
    表示的是第i个矩阵到第j个矩阵相乘的最少步数
    sign[i][j]表示的是第i个矩阵到第j个矩阵相乘的最少步数是由第i个矩阵到第sign[i][j]个矩阵相乘最少步数
    和第sign[i][j]+1个矩阵到第j个矩阵相乘最少步数的得到的最小值！
*/
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[15][15];
int sign[15][15];
int num[15];
int ld[15], rd[15];
int n;

void dfs(int l, int r){//将[l,r]不断分解成最优的子区间
    if(sign[l][r]==0) return ;
    ld[l]++;//l数字出现了多少次，就意味着出现了多少次区间作值为l，也就是出现了多少次左括号
    rd[r]++;//同理r右侧出现了多少次右括弧
    dfs(l, sign[l][r]);
    dfs(sign[l][r]+1, r);
}

void traceBack(){
 
   memset(ld, 0, sizeof(ld));
   memset(rd, 0, sizeof(rd));
   dfs(1, n);
   for(int i=1; i<=n; ++i){
       while(ld[i]--) cout<<"(";
       cout<<"A"<<i;
       while(rd[i]--) cout<<")";
       if(i!=n)
         cout<<" x ";
   }
   cout<<endl;
}

void traceBackTmp(int l, int r){//这是用递归的形式写的，将区间不断缩小，打印(Ai x Aj)
   if(l>r) return;
   if(l==r)  printf("A%d", l);
   else{
      printf("(");
      traceBackTmp(l, sign[l][r]);
      printf(" x ");
      traceBackTmp(sign[l][r]+1, r);
      printf(")");
   }
}

int main(){
    int cnt, count=0;
    string s="";
    s+=10;
    cout<<s<<endl;
    while(scanf("%d", &n) && n){
        int u, v;
        cnt=0;
        scanf("%d%d", &num[cnt], &num[cnt+1]);
        cnt+=2;
        for(int i=2; i<=n; ++i){
           scanf("%d%d", &u, &v);
           num[cnt++]=v;
        }    
        n=cnt-1;
        memset(dp, 0x3f, sizeof(dp));
        memset(sign, 0, sizeof(sign));
        for(int i=1; i<=n; ++i)
           dp[i][i]=0;
        for(int x=2; x<=n; ++x)
          for(int i=1; i+x-1<=n; ++i){
               int j=i+x-1;
               for(int k=i; k<j; ++k){
                   int tt=dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j];
                   if(dp[i][j]>tt){
                      dp[i][j]=tt;
                      sign[i][j]=k;
                   }
               }
          }
    
      cout<<"Case "<<++count<<": ";
      traceBack();

     // cout<<"Case "<<++count<<": ";
     // traceBackTmp(1, n);
     // cout<<endl;
    }
    return 0;
}