• 前言
• 题目大意
• 最长括号匹配
  • 题目描述
• 思路
• 代码
• 总结

前言

一眼区间dp，实际线性dp

题目大意

最长括号匹配

题目描述

对一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配子串。

对100%的数据，字符串长度<=1000000.

思路

第一眼看上去是区间dp模版，咋做我都大概想好了。看了眼数据范围，告辞。$10^6$ 考虑线性dp。

先尝试设一下 $dp[i]$ 为以第 $i$ 位为结尾的最长匹配子串长度。

开始定义了。首先可以看出，由[,(结尾的肯定匹配不上（这是废话），考虑在当前位置为]，)的时候做转移。之后巧的地方要来了。

$i$ 的上一位的长度为 $dp[i-1]$ 对吗，那么我想要添加的话就只要 $a[i-dp[i-1]-1]$ 的位置能和 $a[i]$ 匹配上不就可以加一位了吗。之后只需要再加上 $dp[i-dp[i-1]-2]$，也就是左端点之前连起来的模式即可。总结整理一下。

伪代码：
当 $a[i]==]||a[i]==)$ 时 ：
如果 $a[i]==)\&\&a[i-dp[i-1]-1]==($ 或同理的[]时：
$dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2$

之后在过程中取max和终点即可。很简单了。

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll dp[MAXN];
char a[MAXN];
int main(){
    cin>>(a+1);
    ll n= strlen((a+1)),ans=0,e=0;
    for (int i = 2; i <=n; ++i) {
        if(a[i]==')'||a[i]==']'){
            if((a[i]==')'&&a[i-dp[i-1]-1]=='(')||(a[i]==']'&&a[i-dp[i-1]-1]=='[')){
                dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2;
                if(dp[i]>ans){
                    ans=dp[i];
                    e=i;
                }
            }
        }
    }
    for (ll i = e-dp[e]+1; i <=e ; ++i) {
        cout<<a[i];
    }
    return 0;
}

总结

在很多时候看着好像是区间dp，实际上是线性dp。我们在选择dp方式的时候可以根据数据范围来判断。$10^6$ 已经可以初步判断为线性dp了，$2^n$ 可能是状压dp，$n^3$ 大概是区间dp了。