1 /* 2     题意：矩阵相乘的最少的步数 3     dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j]); 4     表示的是第i个矩阵到第j个矩阵相乘的最少步数 5     sign[i][j]表示的是第i个矩阵到第j个矩阵相乘的最少步数是由第i个矩阵到第sign[i][j]个矩阵相乘最少步数 6     和第sign[i][j]+1个矩阵到第j个矩阵相乘最少步数的得到的最小值！ 7 */ 8 #include<iostream> 9 #include<cstring>10 #include<string>11 #include<cstdio>12 #include<algorithm>13 using namespace std;14 int dp[15][15];15 int sign[15][15];16 int num[15];17 int ld[15], rd[15];18 int n;19 20 void dfs(int l, int r){//将[l,r]不断分解成最优的子区间21     if(sign[l][r]==0) return ;22     ld[l]++;//l数字出现了多少次，就意味着出现了多少次区间作值为l，也就是出现了多少次左括号23     rd[r]++;//同理r右侧出现了多少次右括弧24     dfs(l, sign[l][r]);25     dfs(sign[l][r]+1, r);26 }27 28 void traceBack(){29  30    memset(ld, 0, sizeof(ld));31    memset(rd, 0, sizeof(rd));32    dfs(1, n);33    for(int i=1; i<=n; ++i){34        while(ld[i]--) cout<<"(";35        cout<<"A"<<i;36        while(rd[i]--) cout<<")";37        if(i!=n)38          cout<<" x ";39    }40    cout<<endl;41 }42 43 void traceBackTmp(int l, int r){//这是用递归的形式写的，将区间不断缩小，打印(Ai x Aj)44    if(l>r) return;45    if(l==r)  printf("A%d", l);46    else{47       printf("(");48       traceBackTmp(l, sign[l][r]);49       printf(" x ");50       traceBackTmp(sign[l][r]+1, r);51       printf(")");52    }53 }54 55 int main(){56     int cnt, count=0;57     string s="";58     s+=10;59     cout<<s<<endl;60     while(scanf("%d", &n) && n){61         int u, v;62         cnt=0;63         scanf("%d%d", &num[cnt], &num[cnt+1]);64         cnt+=2;65         for(int i=2; i<=n; ++i){66            scanf("%d%d", &u, &v);67            num[cnt++]=v;68         }    69         n=cnt-1;70         memset(dp, 0x3f, sizeof(dp));71         memset(sign, 0, sizeof(sign));72         for(int i=1; i<=n; ++i)73            dp[i][i]=0;74         for(int x=2; x<=n; ++x)75           for(int i=1; i+x-1<=n; ++i){76                int j=i+x-1;77                for(int k=i; k<j; ++k){78                    int tt=dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j];79                    if(dp[i][j]>tt){80                       dp[i][j]=tt;81                       sign[i][j]=k;82                    }83                }84           }85     86       cout<<"Case "<<++count<<": ";87       traceBack();88 89      // cout<<"Case "<<++count<<": ";90      // traceBackTmp(1, n);91      // cout<<endl;92     }93     return 0;94 }