省选-动态规划-DP 套 DP · Zhl2010 第二博客

常见形式：让你求满足某个条件条件的的数量。

一般是用内层 dp 的结果作为外层 dp 的状态。

首先内层的 $f_{i,j}$ ：

$f_{i,j}=\max\{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[t_i=s_j]\}$

外层 $dp_{i,State，0/1/2}$ 表示确定 $s$ 的前 $i$ 位，状态为 $State$ ，NOI 的匹配完成度。 $State$ 包含 $f_{i,0},f_{i,1},\cdots,f_{i,k}$ 和匹配到第几个字符。

我们还需要一个 $Trans(State,ch)$ 表示在 $State$ 的基础上加上 $s[i+1]=ch$ 会变成什么 $State$ 。 $Trans$ 的计算就相当于是内层 dp 了，直接用 LCS 的转移式，转移完再压缩。

我们怎么压缩 $State$ ？我们发现我们不可能直接存下来，于是...我们观察到相邻的 $f$ 的差值只有可能是 $0/1$ ，所以我们只需要存下来差分数组就行了。

至于代码我是枚举当前的，对之后贡献。

注意：cin>>(c+1); 需要多开两位，char 最后储存了一个 \0。

自动机

我们发现上一道题中，我们把内层 dp 当做了状态，然后就是从 $State$ 转移到 $f_{i,State}$ ，相当于建了一张图，这样的图被称为“自动机”。

然后有合并节点就是两个点能到达的点相同就可以合并。

我们先设出内层 dp 状态： $f_{x,0/1}$ 表示 $x$ 不选/可选可不选的最大独立集。

外层： $f_{x,u,v}$ 表示 $x$ 子树中 $f_{x,0}=u,f_{x,1}=v$ 的方案数。

这样状态会炸掉，所以我们注意到 $0\le u - v \le k$ ，状态就只有 $n*k^2$ 种了。也就是遇到这种问题我们需要去发现冗余状态。所以现在 $f_{s,k,d}$ 表示不选最大集为 $u$ ，可选可不选为 $k+d$ 。

那么转移式子：

$f_{u,k_u,d_u}\times f_{v,k_v,d_v}\to f_{u,k_u+k_v+d_v,\max(0,k_u-k_v)}$