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
     
       9 #include
      
       10 #include
       
        11 #include
        
         12 #include
         
          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"<
          
           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<
           <
            
             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<