题目链接

【题意】

定义如下正规括号序列

• 空序列是正规括号序列
• 如果S是正规括号序列，那么[S], (S)也是正规括号序列
• 如果A和B都是正规括号序列，那么AB也是正规括号序列

输入一个长度不超过100的只有’(‘, ‘)’, ‘[‘, ‘]’组成的字符串序列，添加最少的括号得到一个规则序列，如果有多解输出任意一组即可

【思路】

设将串S变为正规序列至少需要dp(S)个括号，那么

• 如果S的结构是(S’)或[S’]，那么就可以转移到dp(S’)
• 如果S至少有两个字符，那么可以划分为两个部分AB，转移到dp(A)+dp(B)

编程实现的时候，dp(i,j)表示的是把s[i~j]变成正规括号序列所需要添加的最少括号个数，状态转移方程为

dp(i,j)=min{  dp(i+1,j-1), s[i]和s[j]匹配

                  dp(i,k)+dp(k+1,j),i<=k< j }

打印解的时候用递归函数打印，我感觉这个思路很巧妙，自己很难想到，基本上是把紫书的代码抄了一遍，然后下面的代码用C++11能过，用C++会编译错误，会在gets()这里报错，然而并不知道这是为什么

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int inf=2e9;const int maxn=105;char s[maxn];int dp[maxn][maxn];bool match(char c1,char c2){    if(c1=='(' && c2==')') return true;    if(c1=='[' && c2==']') return true;    return false;}void print(int i,int j){
   //打印s[i~j]的解     if(i>j) return;    if(i==j){        if(s[i]=='(' || s[i]==')') printf("()");        else printf("[]");        return;    }    int ans=dp[i][j];    if(match(s[i],s[j]) && ans==dp[i+1][j-1]) {        printf("%c",s[i]);        print(i+1,j-1);        printf("%c",s[j]);        return;    }    for(int k=i;k