题解：P12558 [UOI 2024] Heroes and Monsters

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

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

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

显然，我们选择前 $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)$。十分精妙。