自动搬运

查看原文

来自洛谷，原作者为

	OItby AFO.

搬运于2025-08-24 21:32:11，当前版本为作者最后更新于2020-03-04 21:42:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$PS$

• 博客食用效果更佳
• 欢迎在评论区谔谔，$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]$

说明一下

• $f[i-1]$代表$s[i-1-f[i-1]]$与$s[i]$中间的一段即$s[i-1]$的最长括号匹配
• $2$即$s[i-1-f[i-1]]$与$s[i]$匹配，增加长度为$2$
• $s[i-f[i-1]-2]$即$s[i-f[i-1]-1]$的前一个字符，这里不要漏掉它还可以构成的最长括号匹配的长度
• 不是很复杂，画个图就很明显了

那么若$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;
}