P11588 题解

给定一个带颜色的括号序列，要求选出一个匹配子序列，使得相邻或匹配的括号颜色不同，求能选出的本质不同合法子序列数量。$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)$，好像常数还是不大啊。

见云剪切板。