题解 P1944 【最长括号匹配】

OItby · 2020-03-04 21:42:37 · 题解

博客食用效果更佳
欢迎在评论区谔谔，dalao发现博文有误麻烦在评论区斧正，弱弱感激不尽
~~萌新初学OI(骗管理员神仙的)~~，求管理员通过
蒟蒻写博文不易，请不要直接Ctrl+S→Ctrl+V

对于这题\le 1000000的数据规模显然只允许我们用一重循环

最长，可见这是道最值问题

最值问题可以用贪心，DP，二分，etc

我对于这题用的是DP~~太弱了，只会DP~~

进入正题：如何DP

首先，我们需要构建状态，状态的构建不是唯一的，受最长上升子序列（好题废话）的影响，我是这样构建的

令f[i]表示以s[i]为结尾的字符串的最长括号匹配

接下来，我们就得推状态转移方程

考虑s[i]，要想它能构成括号匹配，很显然地，它肯定不能为(或者[

那么s[i]为)或者]时我们应该怎样转移呢？

我们要找到一个s[k]=((或者[，为了方便叙述，下同)，使得在(k,i)这个开区间内的字符串为最长括号匹配且[k,i]这个闭区间尽可能得大

那么什么情况能满足上面的条件呢？

f[i-1]$表示什么？不正是以$s[i-1]$结尾的最长括号匹配吗，那么如果$s[i-1-f[i-1]]$与$s[i]$匹配的话，$f[i]$一定等于$f[i-1]+2+f[i-f[i-1]-2]

说明一下

2$即$s[i-1-f[i-1]]$与$s[i]$匹配，增加长度为$2
不是很复杂，画个图就很明显了

那么若s[i-1-f[i-1]]与s[i]不匹配怎么办？这时f[i]肯定为0，因为除此之外，不管选哪个字符，都没法满足它和s[i]构成括号匹配

分析千万条，代码第一条，不懂的看一下代码(~~懂得可以自己打去了，偷笑~~)

my~Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

const int L=1000005;
char s[L];
int l,f[L],Ans,id;

int main()
{
    scanf("%s",s+1);//输入，下标从1开始
    l=strlen(s+1);//下标从1开始的字符串长度
    for(int i=2;i<=l;++i)//s[1]显然无法匹配，所以从2开始
        if(s[i]=='('||s[i]=='[') continue;//如分析
        else
            if((s[i]==')'&&s[i-f[i-1]-1]=='(')
            ||(s[i]==']'&&s[i-f[i-1]-1]=='['))
            {
                f[i]=f[i-1]+2+f[i-f[i-1]-2];
                if(f[i]>Ans) Ans=f[i],id=i;//Ans记录最长括号匹配，id记录最长括号匹配的下标
            }
    for(int i=id-Ans+1;i<=id;++i) printf("%c",s[i]);
    putchar('\n');
    return 0;
}