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

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

题目链接：[Brackets Sequence][]  
  
  
题目描述：给出一串由‘（‘）’‘ \[ ' ' \] '组成的串，让你输出添加最少括号之后使得括号匹配的串。  
  
  
分析：是区间dp的经典模型括号匹配。讲解：[http://blog.csdn.net/y990041769/article/details/24194605][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;
    }

[Brackets Sequence]: http://poj.org/problem?id=1141
[http_blog.csdn.net_y990041769_article_details_24194605]: http://blog.csdn.net/y990041769/article/details/24194605