题目描写叙述：

定义合法的括号序列例如以下：

1 空序列是一个合法的序列

2 假设S是合法的序列。则(S)和[S]也是合法的序列

3 假设A和B是合法的序列。则AB也是合法的序列

比如：以下的都是合法的括号序列

(),  [],  (()),  ([]),  ()[],  ()[()]

以下的都是非法的括号序列

(,  [,  ),  )(,  ([)],  ([(]

给定一个由'(',  ')',  '[', 和 ']' 组成的序列，找出以该序列为子序列的最短合法序列。

思路：真是经典的题目。区间DP。题目竟然有陷阱，输入可能是空串,所以用scanf的时候，会不读入，就少了一次读入，wa

所以用gets

//	Accepted	C++	1.002	2015-03-12 13:34:47

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int inf= 0x3f3f3f3f;

int dp[105][105];

char str[105];

int n;

bool match(char a,char b)

{

    if(a=='('&&b==')') return true;

    else if(a=='[' && b==']') return true;

    return false;

}

void print(int l,int r) //递归打印解

{

    if(l>r) return ;

    if(l==r)

    {

        if(str[l]=='('||str[l]==')') printf("()");

        else if(str[l]=='['||str[l]==']') printf("[]");

        return ;

    }

    if(match(str[l],str[r])&&dp[l][r]==dp[l+1][r-1])

    //别忘了match(str[l],str[r])，由于dp[l][r]==dp[l+1][r-1]时候，不一定外側括号匹配，非常easy错

    {

        putchar(str[l]);

        print(l+1,r-1);

        putchar(str[r]);

        return ;

    }

    for(int k=l;k<r;k++)

        if(dp[l][r]==dp[l][k]+dp[k+1][r])

        {

            print(l,k);

            print(k+1,r);

            return;

        }

}

int main()

{

    int T;

    scanf("%d",&T);

    getchar();//吃掉T之后的换行

    while(T--)

    {

        getchar(); //每一个输入前都有一个空行

        gets(str+1);

        n=strlen(str+1);

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;i++) dp[i][i]=1; //边界

        for(int l=1;l<n;l++)

            for(int p=1;p+l<=n;p++)

            {

                dp[p][p+l] = inf ;

                if(match(str[p],str[p+l])) dp[p][p+l]=dp[p+1][p+l-1];

                for(int k=p ; k<p+l ;k++)

                    dp[p][p+l]=min(dp[p][p+l],dp[p][k]+dp[k+1][p+l]);

            }

        if(n) print(1,n);

        puts("");

        if(T) putchar('\n'); //输出之间要输出空行

    }

    return 0;

}