DP套DP
FLY_lai
·
·
算法·理论
把 DP 过程当作状态进行 DP。DP of DP 一般数据范围不会太大，而且一般是计数题。
DP of DP 的本质是自动机上 DP。 大致上可以写作 dp[\dots][S] 表示外层 DP 进行到 \dots 阶段，内层 DP 对应到 S 阶段。
例一：Hero meet devil
题意：给出串 s 和一个数 m。n=|s|。求对于 i=0\sim n，有多少串 t 满足 |t|=m 且 LCS(s,t)=i。n\le 15,m\le 10^3。
假设我们已经知道这是一道 DP 套 DP 的题目。那么对于 DP套DP，最重要的想法就是考虑内层 DP 是怎么进行的？
在这题，内层 DP 是 "最长公共子序列"。平时做 LCS，一般是 f[i][j]=\max(f[i-1][j],f[i][j-1],f[i-1][j-1]+[s_i=t_j])。
考虑完内层 DP，然后就要考虑怎么把内层 DP 的状态压缩入外层 DP 的状态。
因为 t 是变化的，所以 DP 时拿一维记录目前考虑到 t 的第 i 位了；对应的，考虑拿一维 S 记录此时 f[1\sim n][i] 的值。
DP of DP 中，一般数据量较小的那一边作为被压缩的内层 DP。 比如这题，n\le 15，用 S 记录就只用压缩长度 15 的数组了。
但是我们面临第二个问题：怎么用 S 记录此时 f[1\sim n][i] 的值？总不可能开十五维数组。这个点也是大部分 DP of DP 的难点，怎么压缩内层 DP 的状态？这里需要一些神秘的观察。
观察：当 j 固定，f[x+1][j]-f[x][j]\in \{0,1\}。
证明：
按 j 的大小数学归纳法。j=1 显然。
若 f[x+1][j]=f[x][j]，立即成立。
若 f[x+1][j]=f[x][j-1]+1，又 f[x][j]\ge f[x][j-1]，所以 f[x+1][j]-f[x][j]=f[x][j-1]+1-f[x][j]\le f[x][j-1]+1-f[x][j-1]=1。
若 f[x+1][j]=f[x+1][j-1]，f[x][j]\ge f[x][j-1]，由数学归纳法，f[x+1][j-1]-f[x][j-1]\le 1，所以 f[x+1][j]-f[x][j]\le f[x+1][j-1]-f[x][j-1]\le 1。
证毕。
有了这个性质又怎么样？得出结论：\Delta f 是一个 01 序列，所以可以用一个二进制数 S 压缩这个差分数组。
因此可以定义出 dp[i][S]：填 t 的前 i 位，\Delta f[1\sim n][i] 为 S 的方案数。最终 i 的答案就是 \sum dp[m][A]，其中 A 是一个包含 i 个 1 的二进制数。
直接写包 TLE 的，需要预处理出 g[S][ch] 表示 S 的状态下一步填 ch 会怎么样。
例二：BZOJ3591：最长上升子序列
题意：给出 1\sim n 的一个排列的某一个最长上升子序列（记其长度为 m），求原排列可能的种类数。n\le 15。
在这道题目里，内层 DP 就是 "最长上升子序列"。
经过瞪眼法，我们发现 f[i] 表示前 i 个数的 LIS 长度没有好的性质。难道要放弃了吗？
转念想到 LIS 的另一种求法：维护 f_i 表示长度 i 的 LIS 结尾数最小值。而这个数组就有比较好的性质了：它是单调递增的，而且每新加一个数进来，只会修改一个位置。每个数有三种状态：在 f 中，曾经在 f 中，还没考虑。用三进制压缩为 S。
```
#include <bits/stdc++.h>
using namespace std;
const int N = 16;
int n, m;
int a[N], id[N];
int pw[N];
int dp[15000000];
//dp[S]:有多少种a[1~i]的安排方式，使a[1~i]的表格G恰好为S
//i为S中非0个数
//0是没放，1是在序列内，2是已经出了
int getdig(int S, int x) {
for (int i = 1; i <= x; i++)
S /= 3;
return S % 3;
}
int ans = 0;
vector<int> g[3];
int main() {
cin >> n >> m;
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = pw[i - 1] * 3;
for (int i = 1; i <= m; i++) {
cin >> a[i];
a[i]--;
id[a[i]] = i - 1;
}
for (int i = 1; i < m; i++)
if (a[i] > a[i + 1]) {
puts("0");
return 0;
}
dp[0] = 1;
int val[20], LIS[20];
for (int S = 0; S < pw[n]; S++)
if (dp[S]) {
int st = S, cnt = 0, cur = 0;
for (int i = 0; i < n; i++) {
val[i] = getdig(S, i);
if (val[i])
cnt++;
if (val[i] == 1)
LIS[cur++] = i;
}
if (cnt == n) {
ans += dp[S];
continue;
}
for (int i = 0; i < n; i++) {
if (val[i])
continue;
if (id[i] && !val[a[id[i]]])
continue;
int pos = 0;
while (LIS[pos] < i && pos < cur)
pos++;
if (pos == m)
continue;
int SS = S + pw[i];
if (pos < cur)
SS += pw[LIS[pos]];
dp[SS] += dp[S];
}
}
printf("%d\n", ans);
return 0;
}
```
### 例三：[P8352：小 N 的独立集](https://www.luogu.com.cn/problem/P8352)
题意：给一棵树每个结点赋值 $1\sim k$ 的整数。求对于 $i=1\sim nk$，有多少种赋值方式使得这棵树的最大独立集答案为 $i$。对 $10^9+7$ 取模。$n\le 1000,k\le 5$。
DP 套 DP，第一步考虑最大独立集怎么求。$f[i][0/1]$ 表示 $i$ 的子树内 $i$ 强制选/不选的最大独立集。
于是考虑 $dp[i][A][B]$ 表示给 $i$ 的子树赋值，且使得 $f[i][0]=A,f[i][1]=B$ 的方案数。这是可以做的，复杂度为 $O(n^3k^4)$。
考虑优化。观察数据范围里的 $k\le 5$ 很有玄机。因为复杂度瓶颈就在于 $A,B$ 状态定义的复杂度太高了，启发我们用 $k\le 5$ 优化一下。而容易发现 $|A-\max(A,B)|\le k$，因为 $\max(A,B)$ 的方案若 $i$ 选了，把 $i$ 不选就可以得到一个 $A$ 的方案。
所以改为记录 $dp[i][A][\Delta]$ 表示 $i$ 的子树内 $f[i][0]=A$，$\max(f[i][0],f[i][1])-f[i][0]=\Delta$ 的方案数。复杂度降为 $O(n^2k^4)$。
```
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5, MOD = 1e9 + 7;
int n, k;
vector<int> e[N];
int sz[N] = {};
int dp[N][N * 5][6]; //dp[i][j][k]:i子树内，f[i][0]=j,f[i][1]=k 的方案数
int tmp[N * 5][6];
void dfs(int x, int pr) {
sz[x] = 1;
for (int i = 1; i <= k; i++)
dp[x][0][i] = 1;
for (auto v: e[x]) {
if (v == pr)
continue;
dfs(v, x);
memset(tmp, 0, sizeof tmp);
for (int i = 0; i <= k * sz[x]; i++)
for (int j = 0; j <= k; j++) if (dp[x][i][j] != 0)
for (int p = 0; p <= k * sz[v]; p++)
for (int q = 0; q <= k; q++) if (dp[v][p][q] != 0) {
tmp[i + p + q][max(i + j + p, i + p + q) - (i + p + q)]
+= 1ll * dp[x][i][j] * dp[v][p][q] % MOD;
tmp[i + p + q][max(i + j + p, i + p + q) - (i + p + q)] %= MOD;
}
memcpy(dp[x], tmp, sizeof tmp);
sz[x] += sz[v];
}
}
int main() {
cin >> n >> k;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= k * n; i++) {
int ans = 0;
for (int d = 0; d <= min(i, k); d++)
ans = (ans + dp[1][i - d][d]) % MOD;
cout << ans << endl;
}
return 0;
}
```
### 例四：[CF979E：Kuro and Topological Parity](https://codeforces.com/problemset/problem/979/E)
题意：初始有 $n$ 个点，可能为无色/白色/黑色三种情况。现将每个未染色点染色，并添加若干条有向边 $(u,v)$，要求 $u<v$。问有多少种方式使得黑白交替的路径条数 $\bmod 2=p$。$n\le 50$。
这题 $O(n^4)$ 可过，但是我们有 $O(n)$ 解法。
DP 套 DP，先考虑颜色定了，边定了怎么求黑白交替的路径条数。$f_i$ 表示以 $i$ 结尾的黑白交替路径条数。然后求 $\sum f_i$。注意到求的是 $\bmod 2$，所以只关注 $f_i$ 的奇偶性。
然后考虑外层，$dp[i][a][b][c]$ 表示考虑前 $i$ 个点，有 $a$ 个黑点以偶数条黑白交替路径结尾，$b$ 个黑点以奇数条黑白交替路径结尾，$c$ 个白点以偶数条黑白交替路径结尾（实际上就可以推出有 $i-a-b-c$ 个白点以奇数条黑白交替路径结尾）的方案数。
转移时枚举 $i+1$ 作为白奇、白偶、黑奇、黑偶四种情况。统计答案时枚举 $a,b,c$，满足 $(b+d)\bmod 2=p$ 即可。
这就是 $O(n^4)$ 的解法。下面是优化。
如果写出了转移方程，就能发现（简记 $dp[i][a][b][c]$ 为 $dp$）：
1. $i+1$ 白奇，若 $b=0$，无法从 $dp$ 转移而来；否则增加 $dp\times 2^{i-1}$。
1. $i+1$ 白偶，若 $b=0$，增加 $dp\times 2^i$；否则增加 $dp\times 2^{i-1}$。
1. $i+1$ 黑奇，若 $d=0$，增加 $dp\times 2^i$；否则增加 $dp\times 2^{i-1}$。
1. $i+1$ 黑偶，若 $d=0$，无法从 $dp$ 转移而来；否则增加 $dp\times 2^{i-1}$。
因此只要记录 $dp[i][0/1][0/1][0/1]$，表示考虑前 $i$ 个点，$b$ 是否 $>0$，$d$ 是否 $>0$，当前黑白交替路径总数是奇数还是偶数 的方案数。
$O(n^4)$ 代码：
```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 55, MOD = 1e9 + 7;
int n, p;
int clr[N];
ll dp[N][N][N][N];
//dp[i][a][b][c]:a黑偶，b黑奇，c白偶
ll pw[N];
int main() {
cin >> n >> p;
for (int i = 1; i <= n; i++)
cin >> clr[i];
pw[0] = 1;
for (int i = 1; i <= 50; i++)
pw[i] = pw[i - 1] * 2 % MOD;
memset(dp, 0, sizeof dp);
dp[0][0][0][0] = 1;
for (int i = 0; i < n; i++)
for (int a = 0; a <= i; a++)
for (int b = 0; b <= i - a; b++)
for (int c = 0; c <= i - a - b; c++) {
int d = i - a - b - c;
//考虑i+1是什么颜色
if (clr[i + 1] != 1) { //i+1黑色
//i+1黑偶
if (d == 0)
;
else
dp[i + 1][a + 1][b][c] += dp[i][a][b][c] * pw[i - 1] % MOD;
//i+1黑奇
if (d == 0)
dp[i + 1][a][b + 1][c] += dp[i][a][b][c] * pw[i] % MOD;
else
dp[i + 1][a][b + 1][c] += dp[i][a][b][c] * pw[i - 1] % MOD;
}
if (clr[i + 1] != 0) { //i+1白色
//若i+1白偶
if (b == 0)
;
else
dp[i + 1][a][b][c + 1] += dp[i][a][b][c] * pw[i - 1] % MOD;
//若i+1白奇
if (b == 0)
dp[i + 1][a][b][c] += dp[i][a][b][c] * pw[i] % MOD;
else
dp[i + 1][a][b][c] += dp[i][a][b][c] * pw[i - 1] % MOD;
}
dp[i + 1][a + 1][b][c] %= MOD;
dp[i + 1][a][b + 1][c] %= MOD;
dp[i + 1][a][b][c + 1] %= MOD;
}
ll ans = 0;
for (int a = 0; a <= n; a++)
for (int b = 0; b <= n - a; b++)
for (int c = 0; c <= n - a - b; c++) {
int d = n - a - b - c;
if ((b + d) % 2 == p)
ans = (ans + dp[n][a][b][c]) % MOD;
}
cout << ans << endl;
return 0;
}
```