洛谷 题解 UVA1626 【括号序列 Brackets sequence】

看还没有人发记搜的题解，赶紧来水发一篇

我们定义dp[i][j]为区间i~j内最少添加几个括号才能把这个串变成正规括号序列。

考虑四种情况

1. i>j不存在这种子串，返回0

2. i==j子串长度为1无论是"[","]","(",")"都是要消耗1的，返回1

3. s=(s')或s=[s']那么返回的是DP(i+1,j-1)

4. 其他情况，枚举断点，详见代码

至于输出嘛.....不会，看紫书的，输出代码的解释看看楼上吧，这里就不详细解释了

代码:

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int T,n;
string s;
int dp[110][110];//记忆
inline int DP(int l,int r)//记搜
{
    if(l==r)return dp[l][r]=1;//②
    if(l>r)return dp[l][r]=0;//①
    if(dp[l][r]!=INF)return dp[l][r];//记忆化
    if(s[l-1]=='('&&s[r-1]==')'||s[l-1]=='['&&s[r-1]==']')dp[l][r]=min(dp[l][r],DP(l+1,r-1));//③
    for(int i=l;i<r;i++)//枚举i~j的断点
    {
        dp[l][r]=min(dp[l][r],DP(l,i)+DP(i+1,r));//④
    }
    return dp[l][r];
}
inline void print(int l,int r)//输出
{
    if(l>r)return;
    if(l==r)
    {
        if(s[l-1]=='('||s[l-1]==')')
            cout<<"()";
        if(s[l-1]=='['||s[l-1]==']')
            cout<<"[]";
        return;
    }
    if(dp[l][r]==dp[l+1][r-1]&&((s[l-1]=='('&&s[r-1]==')')||(s[l-1]=='['&&s[r-1]==']')))
    {
        cout<<s[l-1];
        print(l+1,r-1);
        cout<<s[r-1];
    }
    else
    {
        for(int i=l;i<r;i++)
        {
            if(dp[l][r]==dp[l][i]+dp[i+1][r])
            {
                print(l,i);
                print(i+1,r);
                return;
            }
        }
    }
}
int main()
{
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        memset(dp,0x3f,sizeof(dp));
        getline(cin,s);
        getline(cin,s);
     //这里要小心，输入的可能是空串！！！！！！！！坑了我很久了
        int n=s.size();
        //cout<<n<<" "<<s<<endl;
        if(!n)
        {
            cout<<endl<<endl;
            continue;
        }
        DP(1,n);
        //cout<<DP(1,n)<<endl;
        print(1,n);
        cout<<endl;
        if(T)cout<<endl;//输出格式也要注意！！
    }
    return 0;
}