题目链接：Brackets Sequence





题目描写叙述：给出一串由‘（‘）’‘ [ ' ' ] '组成的串，让你输出加入最少括号之后使得括号匹配的串。





分析：是区间dp的经典模型括号匹配。解说：http://blog.csdn.net/y990041769/article/details/24194605 ，难点在于要把匹配后的括号输出来。

首先我们知道前面定义dp [ i ] [ j ] 为串中第 i 个到第 j 个括号的最大匹配数目

那么假如我们知道随意 i 到 j 从哪儿插入分点使得匹配加入括号最少。

那么我们定义pos【i】【j】表示 i 到 j 从哪儿分开使得匹配加入括号最少，假设i和j匹配我们能够让pos【i】【j】=-1；

我们发如今我们之前更新dp [ i ] [ j ] 的时候假设中间点k使得if ( dp [ i ] [ k ] + dp [ k+1 ] [ j ] >= dp [ i ] [ j ] ) 。那么我们从k分开能够让加入的括号最少。

可是还要注意一点，考虑全部的都不匹配如“((((”这类。考虑怎么处理，然后就能够递归输出结果。

这题目坑了我非常多次，刚開始Tel，发现所有不匹配不能处理。改了之后wa了。发现输入“（）（（）”。输出的是“（（）（）（））”，明显错误，是在处理的时候没处理好，最后注意输入会有空串。

代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int  N = 120;

int dp[N][N],pos[N][N];   ///i到j从哪个位置分开加入的括号数最少

char s[N];

void show(int i,int j)

{

    if(i>j)  return;

    if(i==j)

    {

        if(s[i]=='('||s[i]==')') cout<<"()";

        else      cout<<"[]";

    }

    else

    {

        if(pos[i][j]==-1)

        {

            cout<<s[i];

            show(i+1,j-1);

            cout<<s[j];

        }

        else

        {

            show(i,pos[i][j]);

            show(pos[i][j]+1,j);

        }

    }

}

int main()

{

    while(gets(s))

    {

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

        int len=strlen(s);

        for(int i=1; i<len; i++)

        {

            for(int j=0,k=i; k<len; j++,k++)

            {

                if(s[j]=='('&&s[k]==')' || s[j]=='['&&s[k]==']')

                {

                    dp[j][k]=dp[j+1][k-1]+2;

                    pos[j][k]=-1;

                }

                for(int f=j; f<k; f++)

                {

                    if(dp[j][f]+dp[f+1][k]>=dp[j][k])  ///注意这里 保证全部都不匹配也可以分

                    {

                        dp[j][k]=dp[j][f]+dp[f+1][k];

                        pos[j][k]=f;

                    }

                }

            }

        }

        //cout<<s.size()-dp[0][s.size()-1]<<endl;

        show(0,len-1);cout<<endl;

    }

    return 0;

}