[CSP-S 2021] 括号序列 题解

Link

对区间 DP 的理解加深了！

常规地，我们设 \(f_{l, r}\) 表示区间 \([l, r]\) 为合法序列的方案数，并从小到大转移。这些内容不太够我们转移啊，而且由于合并顺序的不同还会出现重复的情况：

\[\begin{aligned} \color{red}(A)S(B) \color{green}S(C) \\ \color{green}(A)S \color{red}(B)S(C) \\ \end{aligned} \]

怎么处理这个问题呢？观察一下题目，合法序列可以分为：

1. \(\rm (), (S)\)
2. \(\rm AB, ASB\)
3. \(\rm (A), (SA), (AS)\)

重新设计状态，增加一维限制、或者分开统计：令 \(f_{l, r}\) 表示 \([l, r]\) 为合法序列且 \(l, r\) 所对应字符为匹配的括号；\(g_{l, r}\) 表示 \([l, r]\) 为合法序列且 \(l, r\) 所对应字符不是匹配的括号。分别对应上面的 1, 3 和 2 类。分开统计，最终答案为 \(f_{1, n} + g_{1, n}\)，绕过了这个去重的难点。

令当前的区间长度为 \(len\)，同时 \(O(n^2)\) 地预处理出 \(h(l, r)\) 表示 \([l, r]\) 是否全为 \(\rm */?\)。边界情况为 \(len = 2\) 时 \(f_{l, r} = 1\)，如果 \(l, r\) 中有任意一个不为合法括号则直接跳过。

开始转移

\[f_{l, r} = f_{l, r} + \begin{cases} [h(l, r)] &\text{(S)} \\ f_{l + 1, r - 1} + g_{l + 1, r - 1} &\text{(A)} \\ \sum_{i = 1}^{k} (f_{l + i + 1, r - 1} + g_{l + i + 1, r - 1}) \times h(l + 1, l + i) &\text{(SA)} \\ \sum_{i = 1}^{k} (f_{l + 1, r - i - 1} + g_{l + 1, r - i - 1}) \times h(r - i, r - 1) &\text{(AS)} \\ \end{cases} \]

这四个处理就是字面意思的转移，按照方程式理解就可以了。另外对于 \(\rm ASB, AB\) 有：

\[g_{l, r} = g_{l, r} + \sum_{l \lt i \lt j \lt r, j - i - 1 \leq k} \left( (f_{l, i} + g_{l, i}) \times f_{j, r} \right) \times h(i + 1, j - 1) \]

特判一下 \(\rm AB\) 的情况，定义 \(h(l, l - 1) = 1\)。注意到我们这里钦定 \(B\) 为一三类，为什么这样是对的呢？注意到如果我们不钦定，显然一个合法序列会有多种拆解方式。这种限制方法是有正确性保证的：

1. 完备性：思考一下，任何合法的 \(\rm ASB\) 子串必定能被拆分成形如“封闭/不封闭+符合条件数量*+封闭”的分解方式
2. 不重复性：由于强制钦定了 B 的组成方式，每个序列的分解方式变得唯一了：我们总是选择最外层的括号作为 B 的边界，这确保了不会出现多种解析方式对应同一个序列的情况
3. 边界正确：通过处理 \(h(l, l - 1) = 1\) 保证了空序列的正确性

但是你发现最后这个 \(g\) 的转移是 \(O(n^4)\) 的，怎么优化呢？注意到若 \(i\) 增减 \(1\) 则可取的 \(j\) 的范围也对应地仅增减 \(1\)，对于固定的 \(l, r\)，当 \(i\) 增加时：

• \(j\) 的下界从 \(i + 1\) 变为 \(i + 2\)
• \(j\) 的上界从 \(\min(i + k + 1, r - 1)\)（因为星号序列长度要求为 \(j - i - 1 \leq k\)，考虑两个括号对位置的占用） 变为 \(\min(i + k + 2, r - 1)\)

维护 \(to_i\) 表示 \(\rm A\) 于 \(i\) 结束并于 \(j\) 开始 \(B\) 时 \(j\) 的最大可能取值，再维护一个滑动窗口 \(w\) 表示当前所有可能的 \(f_{j, r}\) 的和，其中 \(j\) 位于滑动窗口中，当 \(i\) 增加时，删除 \(f_{i, r}\) 并将 \(f_{j, r}\) 加入滑动窗口 \(w\)。