黑书上的dp第一题，输出的格式开始打算用记录，tle了，，后来看了这种递归输出。学习，，

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 8 using namespace std; 9 const int inf=0x3f3f3f3f;10 const int maxn=1e2+5;11 int dp[maxn][maxn];12 int path[maxn][maxn];13 char s[maxn];14 void print(int i,int j)15 {16 if(i>j) return ;17 if(i==j)18 {19 if(s[i]=='['||s[i]==']')20 printf("[]");21 else22 printf("()");23 }24 else if(path[i][j]==0)25 {26 printf("%c",s[i]);27 print(i+1,j-1);28 printf("%c",s[j]);29 }30 else31 {32 print(i,path[i][j]);33 print(path[i][j]+1,j);34 }35 }36 int main()37 {38 while(gets(s+1))39 {40 int n=strlen(s+1);41 if(!n) 42 {43 puts("");44 continue;45 }46 for(int i=1;i<=n;i++)47 { 48 dp[i][i-1]=0;49 dp[i][i]=1;50 }51 for(int p=1;p<=n-1;p++)52 {53 for(int i=1;i<=n-p;i++)54 {55 int j=i+p;56 dp[i][j]=inf;57 if((s[i]=='(' && s[j]==')') || (s[i]=='[' && s[j]==']'))58 {59 if(dp[i][j]>dp[i+1][j-1])60 {61 dp[i][j]=dp[i+1][j-1];62 path[i][j]=0;63 }64 }65 for(int k=i;k<=j-1;k++)66 {67 if(dp[i][j]>dp[i][k]+dp[k+1][j])68 {69 dp[i][j]=dp[i][k]+dp[k+1][j];70 path[i][j]=k;71 }72 }73 }74 } 75 print(1,n);76 puts("");77 }78 return 0;79 }