题解 P1944 【最长括号匹配】

$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; } ```