zoj1276 区间dp+路径输出

【题意】：矩阵连乘，找到最小次数，同时输出括号的嵌套方式

【分析】：经典的区间dp，并且记录下了dp的path

因为是递归得到的path，所以递归压栈按从里到外的顺序得到path就可以了

输出嵌套括号部分很好的考察了对栈的理解，和递归执行的顺序。

注意题目输出中有的地方有空格。

【代码】：

 1  //zoj1276 路径输出用到了栈的思想，比较考验思维
 2  #include<iostream>
 3  #include<string.h>
 4  #include<stdio.h>
 5  #define maxn 13
 6  using namespace std;
 7  int N;
 8  int a[maxn],b[maxn],dp[maxn][maxn],path[maxn][maxn];
 9  int cas=0;
10 int DP(int i,int j){
11     if (dp[i][j]!=-1) return dp[i][j];
12      if (i==j) return dp[i][j]=0;
13      int M=99999999;
14     for(int k=i;k+1<=j;k++){
15         int d=DP(i,k)+DP(k+1,j)+a[i]*b[k]*b[j];
16         if (d<M){
17             M=d;
18             dp[i][j]=M;
19             path[i][j]=k;
20         }
21     }
22     return dp[i][j];
23  }
24  void PRINT(int i,int j){
25      if (i<j) printf("(");
26      if (i==j) {
27         printf("A%d",i);
28         return ; //important
29      }
30 
31      PRINT(i,path[i][j]);
32      printf(" x ");
33      PRINT(path[i][j]+1,j);
34 
35      if (i<j) printf(")");
36 
37 }
38  int main(){
39      cas=0;
40      while(~scanf("%d",&N) && N>0){
41          cas++;
42         for(int i=1;i<=N;i++){
43              scanf("%d%d",&a[i],&b[i]);
44          }
45          memset(dp,-1,sizeof(dp));
46          //for(int i=1;i<N;i++) path[i][i+1]=i;
47          printf("Case %d: ",cas);
48          DP(1,N);
49 //         cout<<path[2][3];
50          PRINT(1,N);
51          printf("
");
52 
53      }
54      return 0;
55 
56  }