区间dp模型之括号匹配打印路径 poj（1141）-蒲公英云

区间dp模型之括号匹配打印路径 poj（1141）

小咪咪 2022-08-26 15:27 236阅读 0赞

题目链接：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;
}