M_sea的博客

M_sea的博客

A Mengbier

题解 P4590 【[TJOI2018]游园会】

posted on 2019-07-10 20:16:18 | under 题解 |

DP 套 DP 。


冷静分析一下题目中的几个限制:

  • 只包含 N,O,I
  • 不包含子串 NOI
  • 与一个模板串的 LCS 为 $i$

考虑 DP 。第一个限制可以强制只加这三种字符,第二个限制可以多加一维 0/1/2 表示匹配了多少位,第三个限制可以建一个 LCS 自动机(?)然后在上面转移。


考虑这个自动机怎么建。

先回忆一下两个串的 LCS 怎么求。设 $dp[i][j]$ 表示两个串分别匹配到了第 $i$ 位、第 $j$ 位时的 LCS 长度,转移是 $dp[i][j]=\max\left\{dp[i-1][j],dp[i][j-1],d[i-1][j-1]+[A[i]=B[j]]\right\}$ 。

本题中一个串是固定的,那么转移一次只需要另一个串对应的字符以及前一维的 DP 数组。

注意到 $k\leq 15$ ,可以考虑把所有 DP 值作为自动机的一个节点,然后就可以对应的转移了。

但是这样子点数会非常多,考虑怎么优化。

可以发现 $dp[i]$ 这个数组是单调不降的,并且相邻两个数的差最多为 $1$ 。于是可以状压它的差分数组,点数就是 $2^k$ 级别的了。


然后剩下的就很简单了。设 $f[i][j][k]$ 表示前 $i$ 个字符,匹配到了自动机的 $j$ 节点,和 NOI 匹配了 $k$ 位的方案数,直接枚举填什么字符转移即可。


事实上可以不建出 LCS 自动机,而是每次 DP 时 DP 计算转移,因此这个东西被称为 DP 套 DP 。


代码见 我的blog