1 //Accepted    176 KB    47 ms  2 //感谢大神们为我们这群渣渣铺平前进的道路！！  3 //用scanf("%s",s)!=EOF  WA到死  4 #include <cstdio>  5 #include <cstring>  6 #include <iostream>  7 using namespace std;  8 const int imax_n = 105;  9 const int inf = 100000000; 10 char s[imax_n]; 11 int dp[imax_n][imax_n]; 12 int n; 13 int min(int a,int b) 14 { 15     return a<b?a:b; 16 } 17 int isMatch(char ch1,char ch2) 18 { 19     if (ch1==‘(‘ && ch2==‘)‘) return 1; 20     if (ch1==‘[‘ && ch2==‘]‘) return 1; 21     return 0; 22 } 23 void Dp() 24 { 25     memset(dp,0,sizeof(dp)); 26     for (int i=1;i<=n;i++) 27     { 28         dp[i][i]=1; 29     } 30     for (int i=1;i<n;i++) 31     { 32         if (isMatch(s[i-1],s[i])) dp[i][i+1]=0; 33         else 34         dp[i][i+1]=2; 35     } 36     for (int l=3;l<=n;l++) 37     { 38         for (int i=1;i<=n;i++) 39         { 40             int j=i+l-1; 41             if (j>n) break; 42             dp[i][j]=inf; 43             if (isMatch(s[i-1],s[j-1])) dp[i][j]=dp[i+1][j-1]; 44             if (s[i-1]==‘(‘ || s[i-1]==‘[‘) dp[i][j]=min(dp[i][j],dp[i+1][j]+1); 45             if (s[j-1]==‘)‘ || s[j-1]==‘]‘) dp[i][j]=min(dp[i][j],dp[i][j-1]+1); 46             for (int k=i;k<j;k++) 47             dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); 48         } 49     } 50 } 51 void output(int i,int j) 52 { 53     //printf("s[%d]=%c,s[%d]=%c\n",i,s[i-1],j,s[j-1]); 54     if (i>j) return ; 55     if (dp[i][j]==0) 56     { 57         for (int k=i;k<=j;k++) 58         printf("%c",s[k-1]); 59         return ; 60     } 61     if (dp[i][j]==1 && i==j) 62     { 63         if (s[i-1]==‘(‘ || s[i-1]==‘)‘) 64         printf("()"); 65         if (s[i-1]==‘[‘ || s[i-1]==‘]‘) 66         printf("[]"); 67         return ; 68     } 69     if (dp[i][j]==dp[i+1][j-1] && isMatch(s[i-1],s[j-1])) 70     { 71         printf("%c",s[i-1]); 72         output(i+1,j-1); 73         printf("%c",s[j-1]); 74         return ; 75     } 76     if (dp[i][j]==dp[i+1][j]+1 && (s[i-1]==‘(‘ || s[i-1]==‘[‘)) 77     { 78         printf("%c",s[i-1]); 79         output(i+1,j); 80         if (s[i-1]==‘(‘) 81         printf(")"); 82         else 83         printf("]"); 84         return ; 85     } 86     if (dp[i][j]==dp[i][j-1]+1 && (s[j-1]==‘)‘ || s[j-1]==‘]‘)) 87     { 88         if (s[j-1]==‘)‘) 89         printf("("); 90         else 91         printf("["); 92         output(i,j-1); 93         printf("%c",s[j-1]); 94         return ; 95     } 96     for (int k=i;k<j;k++) 97     if (dp[i][j]==dp[i][k]+dp[k+1][j]) 98     { 99         output(i,k);100         output(k+1,j);101         return ;102     }103     return ;104 }105 int main()106 {107     //while (cin>>s)108     {109         scanf("%s",s);110         n=strlen(s);111         Dp();112         output(1,n);113         printf("\n");114     }115     return 0;116 }