题解：P12558 [UOI 2024] Heroes and Monsters

konyakest · 2025-06-04 13:18:52 · 题解

模拟赛场切了。括号序列上大分。

我们将题目转化为括号匹配模型：将 S 中的怪物看做左括号，英雄看做右括号，则：

• 其他英雄都悲伤的充要条件是：它对应的子括号序列将左括号和右括号对调后是合法的。下文我们称这样的括号序列为“合法逆括号序列”。

根据这个，我们可以把题目转化为：

• 给定一个括号序列，对于每个 k，问有多少种选择 k 个右括号的方式，使得存在一种选择左括号的方式，提取这些选择的左括号、右括号形成的括号序列（以下称作序列 1）是合法的，并且剩余的括号序列（以下称作序列 2）是合法逆括号序列。

显然，我们选择前 k 个左括号一定不劣。

括号序列是可以简单刻画的。我们只需要考虑使用栈匹配括号的过程，记录栈中括号的个数即可刻画其合法性。

分析到这里，我们就有多项式复杂度做法了。我们设 dp_{i,j,k} 考虑了前 i 个，序列 1 的栈中有 j 个左括号，序列 2 的栈中有 k 个右括号的方案数。

我们发现，j,k 存在线性关系，而 i 蕴含了序列 1 的左括号个数，结合 j 可以推出右括号数量，从而此 dp 的复杂度为 O(n^2)。做 k 次即为 O(n^3)。

做到此处，发现无法优化状态，也不能使用数据结构优化。这使我们怀疑：这个题真的是用 dp 求出答案吗？

这时，转成括号序列的优势就显现出来了。我们很自然地发现，“选前 k 个左括号”这个条件看起来十分严格，以至于我们在 i=1\cdots k 的时候的 dp 像是在摸鱼：dp 是在同时维护两个括号序列的合法性，而此时序列 2 遇到的只有右括号，一定合法。我们维护了个寂寞！

所以，我们可以从 k+1 开始 dp。然后，相似的情况也发生了：第一个序列此时一定选右括号，一定合法。我们又维护了个寂寞！

于是，正解呼之欲出了。我们按照第 k 个左括号作为分界线，前面正着 dp，只维护序列 1 的合法性；后面倒着 dp，只维护序列 2 的合法性。在分界线出做一个类似点乘的东西合并答案。

时间复杂度 O(n^2)。十分精妙。