题解 P1944 【最长括号匹配】
OItby
2020-03-04 21:42:37
$PS$
- [博客](https://www.cnblogs.com/hihocoder/p/12416385.html#%E9%A2%98%E8%A7%A3)食用效果更佳
- 欢迎在评论区**谔谔**,$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$
```cpp
#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;
}
```