P11588 题解

KSCD_ · 2025-11-21 08:01:46 · 题解

题意

给定一个带颜色的括号序列，要求选出一个匹配子序列，使得相邻或匹配的括号颜色不同，求能选出的本质不同合法子序列数量。n\le 700。

题解

如果是下标不同子序列，可以设 f_{l,r} 表示在 [l,r] 内选，强制选 l,r 且内部合法的方案数，之后区间 DP 转移。对于本质不同子序列，考虑最小表示，即对于某种子序列，每一位都尽可能靠前选。这样会限制选的相邻位置 x,y 满足 pre_y\le x，其中 pre_y 表示 y 上次出现的位置。这样是局部限制，可在 DP 过程中满足，最终也只对不存在 pre_l 的 f_{l,r} 统计答案即可。

考虑转移，分为 l,r 匹配和不匹配两种。前者枚举内部选的左右端点 x,y ，不要求 x,y 匹配，限制为 c_l\ne c_r,c_l\ne c_x,c_r\ne c_y,pre_x\le l,pre_r\le y；后者枚举与 l 匹配的 x，再枚举 x 后第一个左括号 y，要求 l,x 匹配，不要求 y,r 匹配，限制为 c_l\ne c_x,c_x\ne c_y,pre_y\le x。对于要求匹配的限制，额外开一维 0,1 表示是否强制匹配即可，复杂度 \mathcal O(n^4)，常数很小。

尝试优化，发现对于方案中相邻的 x,y，固定 y 时后缀 x 合法，但固定 x 时合法的 y 没有规律，似乎不太容易直接前缀和优化。注意到转移时 y 的限制只与 x,r 有关，于是设 g_{x,r},h_{x,r} 分别表示固定 x,r 时，两种转移的合法 y 对应值之和。此时 f_{l,r,1} 只会贡献到 g_{l,t} 和 h_{t,r}，也就是 \mathcal O(n) 个值中。转移时枚举 x 后可以 \mathcal O(1)，于是总复杂度为 \mathcal O(n^3)，好像常数还是不大啊。

代码

见云剪切板。