2020.04.12日常总结——dp题的天下

$\color{green}{\text{洛谷P1944\ \ \ \ \ 最长括号匹配}}$洛谷P1944     最长括号匹配

$\color{blue}{\text{【题意】：}}$【题意】：

$\color{orange}{\text{【两个定义】：}}$【两个定义】：

• 括号匹配的字符串：

  1. (),[] 是括号匹配的字符串。

  2. 若 A 是括号匹配的串，则 (A),[A] 是括号匹配的字符串。

  3. 若 A,B 是括号匹配的字符串，则 AB 也是括号匹配的字符串。

  例如：(),[],([]),()() 都是括号匹配的字符串，而 ][,[(]) 则不是。

• 字符串 $\text{A}$A 的子串是指由 $\text{A}$A 中连续若干个字符组成的字符串。

  例如，A,B,C,ABC,CAB,ABCABC 都是 ABCABC 的子串。空串是任何字符串的子串。

$\color{orange}{\text{【问题描述】：}}$【问题描述】： 给定一个仅由 ()[] 构成的字符串 $\text{A}$A，求其最长的括号匹配子串，要求输出该子串。如有多解，输出开始字符所在位置最靠前的一个。$1 \leq | \text{A} | \leq 1 \times 10^6$1≤∣A∣≤1×106。

$\color{blue}{\text{【思路】：}}$【思路】：

记 $f_i$fi​ 表示考虑第 $i$i 个字符时的最长括号匹配子串，要求该子串也必须以 $i$i 结尾。即 $\text{A}_{i-f_i+1 ..i}$Ai−fi​+1..i​ 是括号匹配子串，且 $f_i$fi​ 最大。

接下来就开始考虑如何转移：

• 当 $\text{A}_i$Ai​ 是 ( 或 [ 时，$f_i=0$fi​=0。为什么？因为以 $i$i 结尾的子串肯定不是括号匹配子串。

• 当 $\text{A}_i$Ai​ 是 ) 或 ] 时，我们的任务是求出一个 $k$k，使得 $\text{A}_{k+1,i-1}$Ak+1,i−1​ 是括号匹配子串且 $\text{A}_{k,i}$Ak,i​ 也是括号匹配子串，同时，$k$k 必须尽可能的小（这样长度才能大）。

  等等，因为 $f_{i-1}$fi−1​ 表示 $\text{A}_{i-f_{i-1} .. i-1}$Ai−fi−1​..i−1​ 是一个括号匹配子串，那么我们是不是可以贪心的让 $\text{A}_{i-1-f_{i-1}}$Ai−1−fi−1​​ 和 $\text{A}_i$Ai​ 匹配呢？

  答案是肯定的。因为如果 $\text{A}_{i-1-f_{i-1}}$Ai−1−fi−1​​ 和 $\text{A}_i$Ai​ 匹配的话，$k=i-1-f_{i-1}$k=i−1−fi−1​ 肯定是最优的。为什么？首先，$\text{A}_{i-1-f_{i-1}.. i}$Ai−1−fi−1​..i​ 肯定是一个括号匹配子串。其次，如果我们在往内扩展的话，肯定不优，如果我们往外可以扩展到另一个 $k'$k′ 的话，那么 $f_{i-1}$fi−1​ 的值就肯定错了（因为 $\text{A}_{k'+1..i-1}$Ak′+1..i−1​ 肯定也是括号匹配子串），不符，排除。

  如果 $\text{A}_{i-1-f_{i-1}}$Ai−1−fi−1​​ 和 $\text{A}_i$Ai​ 不匹配的话，$f_{i}=0$fi​=0。为什么？因为往内扩展时也肯定没有一个地方可以让它到 $i$i 的子串成为括号匹配子串。大家可以画个图或想象一下。

于是，我们就可以 $O(|\text{A}|)$O(∣A∣) 完成这题啦！！！

$\color{blue}{\text{【代码】：}}$【代码】：

$N>1 \times 10^6$N>1×106 即可。