题目大意：给一个有小括号和中括号组成的序列，满足题中的三个条件时，是合法的。不满足时是不合法的，问将一个不合法的序列最少添加几个括号可以使之变成合法的。输出最短合法序列。

题目分析：这是《入门经典》上的一道例题。如果仅让求最短序列是极简单的，定义dp(i,j)表示将区间 i~j 变为合法添加的最小字符数.

　　　　　　则 dp(i,j)=dp(i+1,j-1)   （i与j能匹配时)，　　　　dp(i,j)=min(dp(i,k)+dp(k+1,j))。

但是，输出的时候就比较慢了。从左往右通过比较选择最优方案递归输出（看的书上代码）。

 

代码如下：

# include
     
      # include
      
       # include
       
        # include
        
         using namespace std;char p[105];int dp[105][105];const int INF=100000;bool match(int x,int y){    if(p[x]=='('&&p[y]==')')        return true;    if(p[x]=='['&&p[y]==']')        return true;    return false;}void DP(){    int len=strlen(p);    for(int l=1;l<=len;++l){        for(int i=0;i+l-1
         
          j)        return ;    if(i==j){        if(p[i]=='('||p[i]==')')            printf("()");        else            printf("[]");        return ;    }    int ans=dp[i][j];    if(match(i,j)&&ans==dp[i+1][j-1]){        printf("%c",p[i]);        print(i+1,j-1);        printf("%c",p[j]);        return ;    }    for(int k=i;k
          
           0){ DP(); print(0,len-1); } printf("\n"); if(T) printf("\n"); } return 0;}