跳转至

DP 套 DP

DP 套 DP （DP of DP）指的是将内层 DP 的结果作为外层 DP 的状态的一种方法，常用于求解形如 “使某个 DP 的结果的方案数” 的统计。

例题

P8352 [SDOI/SXOI2022] 小 N 的独立集

给定 \(n\) 个点的树的形态以及点的权值范围 \(k\)，对于任意 \(i \in [1, kn]\)，求有多少种权值分配方案，使得树的最大权独立集大小为 \(i\)。

【数据范围】

对于 \(15 \%\) 的数据， \(n \leq 8\)；
对于 \(30 \%\) 的数据， \(n \leq 30\)；
对于 \(50 \%\) 的数据， \(n \leq 100\)；
对于另外 \(10 \%\) 的数据， \(k=1\)；
对于另外 \(15 \%\) 的数据， \(k=2\)；
对于 \(100 \%\) 的数据， \(n \leq 1000\)， \(k \leq 5\)， \(u_{i}, v_{i} \leq n\)。

【提示】

最大权独立集问题是指：选择一个点集，使得任意两个被选择的点都没有边直接相连，并且使得所有被选择的点的点权之和最大。

  • 经典 dp ( \(n \leq 8\) )：

枚举所有权值分配方案，设 \(f_{u,0/1}\) 表示 \(u\) 子树中点 \(u\) 不选/选的最大独立集然后做经典树上最大权独立集 dp 即可，复杂度 \(O(nk^n)\)。

  • dp 套 dp ( \(n \leq 100\) )：

经典 dp 和极小的值域 ( \(k \leq 5\) ) 启发我们可以将 \(f_{u,0/1}\) 的值设为状态。

设 \(g_{u,v_0,v_1}\) 为 \(u\) 子树中 \(f_{u,0}, f_{u,1}\) 分别为 \(v_0, v_1\) 时的方案数。转移时考虑将 \(u\) 的一个儿子 \(v\) 合并到 \(u\) 中，枚举 \(i, j, p, q\) 分别作为 \(f_{u,0}, f_{u,1}, f_{v,0}, f_{v,1}\)，易得转移：

\[ g'_{u,i+\max(p,q),j+p} \leftarrow g'_{u,i+\max(p,q),j+p} + g_{u,i,j} \times g_{v,p,q} \]

套用树上背包的复杂度分析可得时间复杂度为 \(O(n^3k^4)\)，能够通过 \(n \leq 100\)。

  • 状态优化 ( \(n \leq 1000\) )：

上文的 dp 方法复杂度瓶颈在于状态数就已经到达了 \(O(n^3k^2)\) 级别，此时可以考虑简化内层 \(f\) 的状态和转移。考虑另一种树上最大权独立集的 dp 方法：重新定义 \(f_{u,0/1}\) 表示 \(u\) 子树内是 \((1)\) 否 \((0)\) 强制不选节点 \(u\) 时的最大方案大小，转移显然，如此设便得到了一条重要性质： \(0 \leq f_{u,0} - f_{u,1} \leq \text{val}_u \leq k\)（强制不选的答案肯定小于等于无限制的答案，且两者一定不会差出 \(u\) 点的权值），此时自然得出 \(g_{u,v_1,d}\) 表示 \(u\) 子树中 \(f_{u,0}, f_{u,1}\) 分别为 \(v_1 + d, v_1\) 时的方案数，依然枚举 \(i, j, p, q\)，有转移：

\[ g'_{u,i+p+q,\max(i+j+p,i+p+q)-(i+p+q)} \leftarrow g'_{u,i+p+q,\max(i+j+p,i+p+q)-(i+p+q)} + g_{u,i,j} \times g_{v,p,q} \]

时间复杂度 \(O(n^2k^4)\)。

实现 
 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
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int ll
#define mst(u, val) memset(u, val, sizeof(u))
#define mcp(from, to) memcpy(to, from, sizeof(to))
typedef long long ll;
typedef const int cint;
constexpr int MAXN = 1e3 + 10, mod = 1e9 + 7;
template <typename T> inline void chkmx(T &a, const T b) { a = a < b ? b : a; }
template <typename T> inline void chkmn(T &a, const T b) { a = a > b ? b : a; }
template <typename T> inline void add(T &a, const T b) { a = ((a + b) % mod + mod) % mod; }
template <typename T> inline void mul(T &a, const T b) { a = ((a * b) % mod + mod) % mod; }
vector<int> e[MAXN];
int n, k, f[MAXN][MAXN * 5][6], g[MAXN * 5][6], siz[MAXN];
void dfs(cint u, cint fa)
{
    siz[u] = 1;
    for (int i = 1; i <= k; i++) f[u][0][i] = 1;
    for (cint v : e[u])
        if (v ^ fa)
        {
            dfs(v, u), mst(g, 0);
            for (int i = 0; i <= k * siz[u]; i++)
                for (int j = 0; j <= k; j++)
                    if (f[u][i][j])
                        for (int p = 0; p <= k * siz[v]; p++)
                            for (int q = 0; q <= k; q++)
                                if (f[v][p][q])
                                    add(g[i + p + q][max(i + j + p, i + p + q) - (i + p + q)], f[u][i][j] * f[v][p][q]);
            mcp(g, f[u]), add(siz[u], siz[v]);
        }
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int u, v, i = 1; i < n; i++) cin >> u >> v, e[u].emplace_back(v), e[v].emplace_back(u);
    dfs(1, 0);
    for (int i = 1; i <= k * n; i++)
    {
        int ans = 0;
        for (int j = 0; j <= min(i, k); j++) add(ans, f[1][i - j][j]);
        cout << ans << endl;
    }
    return 0;
}
P4590 [TJOI2018] 游园会

小豆参加了 NOI 的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是 \(\texttt{N}\)、 \(\texttt{O}\)、 \(\texttt{I}\) 的字样。在会场上他收集到了 \(K\) 个奖章组成的串。兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。现在已知兑奖串长度为 \(N\)，并且在兑奖串上不会出现连续三个奖章为 \(\texttt{NOI}\)，即奖章中不会出现子串 \(\texttt{NOI}\)。现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。

可能这个数会很大，结果对 \(10^9+7\) 取模。

对于 \(100\%\) 的数据，\(N\leq 1000,K \leq 15\)。

下面称输入给出的奖章串为 \(s\)，要求的兑奖串为 \(t\)。

会发现题目中的 \(t\) 有三个限制：

  1. 长度为 \(N\)，且只有 \(\texttt{N}\)、 \(\texttt{O}\)、 \(\texttt{I}\) 三个字符。
  2. \(s\) 与 \(t\) 的 LCS 为 \(len\)。
  3. 不能出现子串 \(\texttt{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\) 的 LCS 是否为 \(i\) 的。

显然就是先求出 \(t\) 的 LCS 再判断。

这是一个经典 dp，设 \(f_{i,j}\) 表示 \(t[1,i]\) 和 \(s[1,j]\) 匹配的 LCS，转移：

\[ 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\) 再做一遍 LCS 的那个 dp，得到新的状态 \(S'\)（即内层 dp \(f\) 数组的第 \(i+1\) 行）。

这样就转移成功了。

但是很明显 \(S\) 的数量太多了，时间空间双爆炸。

但显然并不是所有的 \(S\) 都是合法的。

因为 \(0 \leq f_{i,j} - f_{i,j-1} \leq 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)\)。

实现 
 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
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int ll
typedef long long ll;
typedef const int cint;
constexpr int MAXN = 1e3 + 5, mod = 1e9 + 7;
int n, k, dp[2][(1 << 15) + 5][3], f1[20], f2[20], ans[20];
char s[20];
template <typename T> inline void add(T &a, const T b) { a = ((a + b) % mod + mod) % mod; }
int encrypt(cint *f)
{
    int S = 0;
    for (int i = 0; i < k; i++) S += (f[i + 1] - f[i]) * (1ll << i);
    return S;
}
void decrypt(int *f, cint S)
{
    for (int i = 0; i < k; i++) f[i + 1] = S >> i & 1;
    for (int i = 1; i <= k; i++) f[i] += f[i - 1];
}
void DP(cint S, cint newi, cint newj, char c, cint val)
{
    decrypt(f1, S);
    for (int i = 1; i <= k; i++) f2[i] = max({f2[i - 1], f1[i], f1[i - 1] + (c == s[i])});
    add(dp[newi & 1][encrypt(f2)][newj], val);
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> k >> (s + 1), dp[0][0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int S = 0; S < (1 << k); S++) dp[i & 1 ^ 1][S][0] = dp[i & 1 ^ 1][S][1] = dp[i & 1 ^ 1][S][2] = 0;
        for (int S = 0; S < (1 << k); S++)
        {
            if (dp[i & 1][S][0])
            {
                DP(S, i + 1, 1, 'N', dp[i & 1][S][0]);
                DP(S, i + 1, 0, 'O', dp[i & 1][S][0]);
                DP(S, i + 1, 0, 'I', dp[i & 1][S][0]);
            }
            if (dp[i & 1][S][1])
            {
                DP(S, i + 1, 1, 'N', dp[i & 1][S][1]);
                DP(S, i + 1, 2, 'O', dp[i & 1][S][1]);
                DP(S, i + 1, 0, 'I', dp[i & 1][S][1]);
            }
            if (dp[i & 1][S][2])
            {
                DP(S, i + 1, 1, 'N', dp[i & 1][S][2]);
                DP(S, i + 1, 0, 'O', dp[i & 1][S][2]);
            }
        }
    }
    for (int S = 0; S < (1 << k); S++) add(ans[__builtin_popcount(S)], ((dp[n & 1][S][0] + dp[n & 1][S][1]) % mod + dp[n & 1][S][2]) % mod);
    for (int i = 0; i <= k; i++) cout << ans[i] << endl;
    return 0;
}