做过不少 DP of DP 题，但是考试还是想不到，很气，写个总结记录下。
对于一个题目，如果它要求的是在某个限制下计数，并且在看一个状态有没有满足限制的时候也需要 DP，这时候往往就要用到 DP of DP。
一般的流程是这样的，我们先考虑对于一个已知状态，怎么判定其是否满足性质。这时候我们一般都会有一个 DP，且这个 DP 是用增量法填表的，即类似于 \(f_{i,...}\) 表示前 \(i\) 个位置（或其它）怎么怎么样。然后因为我们的根本需求是计数，而计数我们也用到增量法，所以可以把 \(f_{i,...}\) 的 \(i\) 放到外层 DP 处，然后把剩下的 \(f_{...}\) 给排成一列压缩起来，变成一个状态。这样在外层我们就得到了 \(F_{i,S}\)，表示考虑前 \(i\) 个位置（或其它），内层 DP 的状态是 \(S\) 的方案数。在转移 \(i+1\) 的时候，我们把 \(S\) 还原成内层 DP 数组 \(f_{...}\)，然后对 \(f_{...}\) 和 \(i+1\) 跑内层 DP 得到一个新状态\(f^{'}_{...}\) 并重新压缩成 \(T\)，这样就可以从 \(F_{i,S}\) 转移到 \(F_{i+1,T}\)。
考虑看一道例题：
给一个小写字母字符串 \(S\)，\(|S|\leq15\)，问有多少个长度为 \(n\)，\((n\leq 100)\) 的小写字母字符串 \(T\)，使得 \(S\) 和 \(T\) 的最长上升子序列的长度为 \(k\)。对于 \(k=0,1,2...|S|\) 都要求答案。
经典题，按照上面的流程来做。
首先对于一个已知字符串 \(T\)，考虑求它的最长上升子序列。设 \(f_{i,j}\) 表示考虑 \(T\) 的前 \(i\) 个字符，\(S\) 的前 \(j\) 个字符的最长上升子序列最长是多少。这个 DP 符合增量法，所以把 \(f_{1,2...j}\) 压缩成一个状态 \(S\)。在外层，设 \(F_{i,S}\) 表示考虑 \(T\) 的前 \(i\) 个字符，\(f_{i,\{0,1...|S|\}}\) 算出来的值状压起来为 \(S\) 的方案数。转移的时候，枚举下一个字符填什么，然后把 \(S\) 还原成 \(f\)，然后计算出新的 \(f'\)，再状压回 \(T\)，就可以从 \(F_{i,S}\) 转移到 \(F_{i+1,T}\) 了。
这样我们就完成了普通的 DP of DP，但是这样复杂度有问题，因为 \(f\) 的取值范围是 \([0,15]\) 压起来特别大，但是我们发现 \(f_i-f_{i-1}\in[0,1]\)，所以可以把 \(f_i-f_{i-1}\) 压起来，这样 \(F_{i,S}\) 的 \(S\) 的取值只有 \(2^{15}\) 了。
代码如下，这里只实现了字符集为 \(\{N,O,I\}\) 。原题是 [TJOI2018] 游园会。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| #include <bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define RI register int
typedef long long LL;
#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);
using namespace std;
int const mod = 1e9 + 7;
char s[20];
int f[20], g[20];
int Trans[1 << 15][3];
int dp[2][3][1 << 15];
int bitcnt[1 << 15];
int Ans[20];
inline void Add(int &x, int y) { x += y - mod, x += (x >> 31) & mod; }
int main() {
#ifdef LOCAL
FILEIO("a");
#endif
int n, k; scanf("%d %d", &n, &k);
scanf("%s", s + 1);
for (RI S = 0, NS; S < (1 << k); ++S) {
for (RI i = 1; i <= k; ++i)
f[i] = f[i - 1] + ((S >> (i - 1)) & 1);
for (RI i = 1; i <= k; ++i)
g[i] = max(g[i - 1], max(f[i], f[i - 1] + (s[i] == 'N')));
NS = 0;
for (RI i = 1; i <= k; ++i)
NS |= (g[i] - g[i - 1]) << (i - 1);
Trans[S][0] = NS;
for (RI i = 1; i <= k; ++i)
g[i] = max(g[i - 1], max(f[i], f[i - 1] + (s[i] == 'O')));
NS = 0;
for (RI i = 1; i <= k; ++i)
NS |= (g[i] - g[i - 1]) << (i - 1);
Trans[S][1] = NS;
for (RI i = 1; i <= k; ++i)
g[i] = max(g[i - 1], max(f[i], f[i - 1] + (s[i] == 'I')));
NS = 0;
for (RI i = 1; i <= k; ++i)
NS |= (g[i] - g[i - 1]) << (i - 1);
Trans[S][2] = NS;
}
int cur = 1, nxt = 0;
dp[0][0][0] = 1;
for (RI i = 0; i < n; ++i) {
swap(cur, nxt);
memset(dp[nxt], 0, sizeof(dp[nxt]));
for (RI S = 0; S < (1 << k); ++S) {
Add(dp[nxt][1][Trans[S][0]], dp[cur][0][S]);
Add(dp[nxt][1][Trans[S][0]], dp[cur][1][S]);
Add(dp[nxt][1][Trans[S][0]], dp[cur][2][S]);
Add(dp[nxt][0][Trans[S][1]], dp[cur][0][S]);
Add(dp[nxt][2][Trans[S][1]], dp[cur][1][S]);
Add(dp[nxt][0][Trans[S][1]], dp[cur][2][S]);
Add(dp[nxt][0][Trans[S][2]], dp[cur][0][S]);
Add(dp[nxt][0][Trans[S][2]], dp[cur][1][S]);
}
}
for (RI S = 1; S < (1 << k); ++S)
bitcnt[S] = bitcnt[S ^ (S & (-S))] + 1;
for (RI i = 0; i < 3; ++i)
for (RI S = 0; S < (1 << k); ++S)
Add(Ans[bitcnt[S]], dp[nxt][i][S]);
for (RI i = 0; i <= k; ++i)
printf("%d\n", Ans[i]);
return 0;
}
|
但是我们肯定不仅仅满足这个普通的 DP of DP，我们需要更便捷的东西——自动机。
也就是说我们干脆就直接把 \(S\) 看成是一个状态的集合，然后把所有的状态的集合建出一个转移的自动机。一个自动机上面的节点代表着一个状态，而转移边就代表着这个状态加入一个东西后可以转移到哪里。这样我们的 DP 就变成了一个普通的自动机上 DP。
典型例子是 [ZJOI2019] 麻将，可以结合我的这篇博客把这个题切了。
（不知为何写着写着就变成一个普及 DP of DP 的博客了……）