dp 套 dp（dp of dp）
简要介绍dp of dp 的题的形式一般是让你求满足...条件的...的数量。
直接 dp 可能不是很好用一个状态来刻画是否满足条件。
但是判定一个东西是否满足条件可以用一个比较简单的 dp 来处理。
这样我们可以用内层 dp 的结果作为外层 dp 的状态，就容易刻画出满足...条件这个限制了。
因为我不会自动机，就用普通 dp 的术语来描述了。
这么说还是很抽象，所以我们通过几道例题来进一步解析。
I. 游园会
这应该算是 dp 套 dp 板子。
下面称输入给出的奖章串为 \(s\)，要求的兑奖串为 \(t\)。
会发现题目中的 \(t\) 有三个限制：
[*]长度为 \(N\)，且只有 N,O,I 三个字符。
[*]与 \(s\) 的 LIS 为 \(len\)。
[*]不能出现子串 NOI。
会发现限制 \(1\) 可以直接在 dp 转移的时候满足，限制 \(3\) 直接多加一维状态 \(0/1/2\) 表示现在的后缀和 NOI 的匹配位数即可。
即我们的 dp 状态应该是 \(dp_{i,S,0/1/2}\) 表示填到 \(t\) 的第 \(i\) 位，当前状态是 \(S\)，后缀和 NOI 的匹配位数是 \(0/1/2\) 的方案数。
但是限制 \(2\) 极其不好记录状态，因为你需要知道当前匹配到 \(s\) 的第几位，而直接记录匹配到 \(s\) 的第几位的话又容易算重。
考虑我们是怎么判定一个给定的 \(t\) 和 \(s\) 的 LIS 是否为 \(i\) 的。
显然就是先求出他们的 LIS 再判断。
这是一个经典 dp，设 \(f_{i,j}\) 表示 \(t\) 和 \(s\) 匹配的 LIS，转移：
\(f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+(t_i==s_j))\)。
发现我们要计算出 \(f\) 第 \(i\) 行的所有值，需要的只是 \(t_i\) 和 \(f\) 第 \(i-1\) 行的所有值。
所以最外层 dp 的状态的 \(S\) 我们直接让他表示内层 dp 的第 \(i\) 行的所有值。
外层 dp 的转移就枚举下一个位置 \(t_{i+1}\) 是什么，并对第二维 \(S\) 再做一遍 LIS 的那个 dp，得到新的状态 \(S'\)（即内层 dp \(f\) 数组的第 \(i+1\) 行）。
这样就转移成功了。
但是很明显 \(S\) 的数量太多了，时间空间双爆炸。
但显然并不是所有的 \(S\) 都是合法的。
因为 \(0\le f_{i,j}-f_{i,j-1}\le 1\)，所以 \(S\) 表示的序列的差分数组每一位都一定是 \(0/1\)。
因此状态 \(S\) 可以改为记录内层 dp \(f\) 数组的第 \(i\) 行的差分数组。
进一步地，可以直接状压成一个二进制数。
这样 \(S\) 的总数就是 \(2^K\) 了。
状态数是 \(O(N2^K)\)，转移在 \(O(1)\) 枚举完 \(t_{i+1}\) 之后需要对内层 dp 进行 \(O(K)\) 的转移。
复杂度 \(O(NK2^K)\)。
转移好函数的封装并不难写，实现参考了第一篇题解。
注意滚动数组并稍微剪枝。
因为在进行外层 dp 转移的时候还要对内层 dp 进行一次转移，所以叫 dp 套 dp。
code：
#includeusing namespace std;const int N=1e3+5,mod=1e9+7;inline int read(){ int w=1,s=0; char c=getchar(); for(;c'9';w*=(c=='-')?-1:1,c=getchar()); for(;c>='0'&&c
页:
[1]