跳转至

DP 套 DP

DP 套自动机

CF750E New Year and Old Subsequence

题解链接

上面的例题中使用的 dp 状态可以看成一个自动机：

DPDP

这个自动机可以处理题目的限制。我们只需要在 DP 状态中记录当前在自动机的哪个节点，然后按照字符来转移即可。

DP 套 DP

P4590 [TJOI2018] 游园会

题意

有两个字符串 \(s\) 和 \(t\)，长度分别为 \(n\) 和 \(k\)，保证只包含 'A','B','C' 三种字母。要求 \(s\) 中不能包含连续的 "ABC" 子串。对于一组 \((s,t)\)，你的得分为 \(s\) 和 \(t\) 的最长公共子序列长度。

现在给定 \(n,k\) 和字符串 \(t\)，请对于所有 \(x\in[0,k]\) 求出，得分为 \(x\) 时可能的字符串 \(s\) 有多少个。答案对 \(10^9+7\) 取模。

\(n\le 1000,\ k\le 15\)

注意到数据范围较小，考虑 dp。"ABC" 连续子串的限制容易处理，我们只需要在 dp 中加入一个 \(0/1/2\) 的状态，表示匹配 "ABC" 的长度即可。

考虑如何处理 \(\operatorname{lcs}\) 的限制，然而没有能够处理 \(\operatorname{lcs}\) 的自动机。考虑朴素的 \(\operatorname{lcs}\) 问题，一般情况下，我们会使用一种 \(O(nm)\) 的 dp 来解决 \(\operatorname{lcs}\) 问题。这个 dp 的状态是：\(g_{i,j}\) 表示第一个串的前缀 \(i\) 和第二个串的前缀 \(j\) 的 \(\operatorname{lcs}\)。我们现在希望计数：使得 \(g_{n,k}=x\) 的串 \(s\) 有多少个。

由于我们现在要计数 \(s\)，因此我们枚举 \(s\) 的下标 \(i\)，依次决策每一个 \(s_i\) 填哪个字符。由于 \(g_{n,k}=x\) 是钦定的约束，因此我们可以将 \(g\) 的值记入外层 dp 的状态：设 \(f_{i,g,z}\) 表示考虑 \(s\) 的前 \(i\) 位，内层 dp 的 dp 值为 \(g\)，匹配 "ABC" 的情况为 \(z\)，对应的方案数有多少。

写出大致的转移：

\[ f[i,g,z]\to f[i+1,\delta_1(g,c),\delta_2(z,c)] \]

然而如果记录整个 \(g\)，状态数将达到 \(|\Sigma|n(k)^{nk}\)。考虑优化，观察 \(g\) 的转移方程：

\[ g[i,j]=\max\big(g[i-1,j],\ g[i,j-1],\ g[i-1,j-1]+[s_i=t_j]\big) \]

注意到，\(g[i]\) 的转移只需要用到 \(g[i-1]\)，并且我们最终也只需要用到 \(g[n,k]\)。因此，我们可以只保留一行 \(g[i]\) 的值。此时状态数减少为 \(|\Sigma|n(k)^k\)，仍需进一步优化。

直觉告诉我们，一行 \(g[i]\) 的 \((k)^{k}\) 种状态仍有大量无效状态。考虑一行 \(g[i]\) 的实际含义：依次加入 \(t[j]\)，更新 \(s\) 和 \(t[1\sim j]\) 的 \(\operatorname{lcs}\)。显然，加入一个字符不会导致 \(\operatorname{lcs}\) 变短，同时也不会增大超过 \(2\)。因此，一行 \(g[i]\) 数组相邻位置的 dp 值之差只能为 \(\{0,1\}\)。

这样，一行就只剩下 \(2^k\) 种状态。我们用一个二进制数来状压 \(g[i]\) 的差分数组；通过暴力解压预处理出 \(\delta_1(g[i],c)\) 的所有结果，即可做到 \(O(1)\) 转移。

总状态数达到了 \(|\Sigma|n2^k\)，每个状态转移 \(|\Sigma|\) 次，总时间复杂度 \(O(|\Sigma|^2n2^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
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
#include<iostream>
#include<cstring>
#include<bitset>
#define bs bitset<5>
#define ll long long
using namespace std;
const int N = 1010;
const int K = 15;
const int MOD = 1e9 + 7;

int n, k;
int a[K];
string t;

int trans[1 << K][3], cnt[1 << K];
int pre[K], cur[K];

int f[1 << K][3], g[1 << K][3];
int ans[K + 2];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    cin >> t;

    for(int i = 0; i < (int)t.size(); i++) {
        if(t[i] == 'N') a[i] = 0;
        else if(t[i] == 'O') a[i] = 1;
        else a[i] = 2;
    }

    for(int i = 1; i < (1 << k); i++) cnt[i] = cnt[i ^ (i & -i)] + 1;

    for(int i = 0; i < (1 << k); i++) {
        pre[0] = i & 1;
        for(int j = 1; j < k; j++) {
            pre[j] = pre[j - 1] + (bool)(i & (1 << j));
        }
        for(int c = 0; c < 3; c++) {
            cur[0] = max(pre[0], (int)(a[0] == c));
            for(int j = 1; j < k; j++) {
                cur[j] = max(max(cur[j - 1], pre[j]), pre[j - 1] + (a[j] == c));
            }
            int sta = 0;
            sta += cur[0];
            for(int j = 1; j < k; j++) {
                sta += (cur[j] - cur[j - 1]) * (1 << j);
            }
            trans[i][c] = sta;
        }
    }

    g[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < (1 << k); j++) {
            for(int z = 0; z < 3; z++) {
                f[j][z] = g[j][z];
                g[j][z] = 0;
            }
        }
        for(int j = 0; j < (1 << k); j++) {
            for(int z1 = 0; z1 < 3; z1++) {
                for(int c = 0; c < 3; c++) {
                    int z2 = (c == z1) ? z1 + 1 : (c == 0 ? 1 : 0);
                    if(z2 >= 3) continue;
                    (g[trans[j][c]][z2] += f[j][z1]) %= MOD;
                }
            }
        }
    }

    for(int j = 0; j < (1 << k); j++) {
        (ans[cnt[j]] += ((ll)g[j][0] + g[j][1] + g[j][2]) % MOD) %= MOD;
    }

    for(int i = 0; i <= k; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Y7-1 基因相似度

本题为上一题的弱化版，没有连续子串 "ABC" 的限制。

代码 
 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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
const int M = 15;
const int MOD = 1e9 + 7;

int T;
int n, m;
int a[M];
string s;

int trans[1 << M][4];
int pre[M], cur[M];

int ans[M + 2];
int f[1 << M], g[1 << M];
int cnt[1 << M];

int work() {

    for(int i = 0; i < (1 << m); i++) {
        pre[0] = (i & 1);
        for(int j = 1; j < m; j++) {
            pre[j] = pre[j - 1] + (bool)(i & (1 << j));
        }
        for(int c = 0; c < 4; c++) {
            cur[0] = max(pre[0], (int)(c == a[0]));
            for(int j = 1; j < m; j++) {
                cur[j] = max(max(cur[j - 1], pre[j]), pre[j - 1] + (bool)(a[j] == c));
            }
            int sta = 0;
            sta += cur[0];
            for(int j = 1; j < m; j++) {
                sta += (cur[j] - cur[j - 1]) * (1 << j);
            }
            trans[i][c] = sta;
        }
    }

    for(int i = 0; i < (1 << m); i++) f[i] = g[i] = 0;
    g[0] = 1;

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < (1 << m); j++) f[j] = g[j];
        for(int j = 0; j < (1 << m); j++) g[j] = 0;
        for(int j = 0; j < (1 << m); j++) {
            for(int c = 0; c < 4; c++) {
                (g[trans[j][c]] += f[j]) %= MOD;
            }
        }
    }

    for(int i = 0; i <= m; i++) ans[i] = 0;
    for(int i = 0; i < (1 << m); i++) {
        (ans[cnt[i]] += g[i]) %= MOD;
    }

    for(int i = 0; i <= m; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

int main() {

    for(int i = 1; i < (1 << M); i++) cnt[i] = cnt[i ^ (i & -i)] + 1;

    cin >> T;
    while(T--) {
        cin >> s >> n;
        m = s.size();
        for(int i = 0; i < m; i++) {
            if(s[i] == 'A') a[i] = 0;
            else if(s[i] == 'T') a[i] = 1;
            else if(s[i] == 'C') a[i] = 2;
            else a[i] = 3;
        }
        work();
    }

    return 0;
}

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

题意

有一棵 \(n\) 个节点的树，点有点权，点权是 \([1,k]\) 区间内的整数。请你对所有 \(x\in [1,nk]\) 求出，钦定树的最大权独立集为 \(x\)，对应有多少种赋值点权的方案。答案对 \(10^9+7\) 取模。

\(n\le 1000,\ k\le 5\)

先考虑最大权独立集的 dp 做法：设 \(g_{i,0/1}\) 表示考虑 \(i\) 子树，钦定不选/选择 \(i\) 号节点，最大独立集是多少。

按照 dp 套 dp 的思路，我们设外层 dp 的状态：\(f[i,g_{i,0},g_{i,1}]\) 表示 \(i\) 子树内，钦定选和不选节点 \(i\) 的最大权独立集分别为 \(g_{i,0}\) 和 \(g_{i,1}\)，对应的点权方案数有多少。

然而，这样状态数将达到 \(n(nk)^2\)，需要优化。

考虑将 \(g_{i,0/1}\) 两个状态压缩。差分是一种比较通用的思路，因此我们注意到 \(g_{u,0}\ge g_{u,1}-k\)。然而我们无法保证 \(g_{u,0}\) 和 \(g_{u,1}\) 的大小关系。因此，我们可以记 \(h_{u,0}=g_{u,0}\)，\(h_{u,1}=\max(g_{u,0},g_{u,1})\)。这样，我们一定有 \(h_{u,1}-k\le h_{u,0}\le h_{u,1}\)。

因此设 \(f_{u,i,j}\) 表示 \(u\) 子树内，最大独立集 dp 的状态为 \(h_{u,0}=i,\ h_{u,1}=i+d\)，对应的方案数。其中 \(i\in [1,nk]\)，\(j\in [0,k]\)。

考虑求解朴素的最大独立集时，如何处理 \(h\) 的转移。显然有：

\[ \begin{align*} h_{u,0}&=\sum_{v\in to[u]}h_{v,1}\\ h_{u,1}&=\sum_{v\in to[u]}h_{v,0}+w_u \end{align*} \]

容易写出 \(f\) 的转移：

\[ f[u,i,j]\times f[v,p,q]\to f'\big[u,\ i+p+q,\ \max(j-q,0)\big] \]

考虑使用树上背包分析其时间复杂度。由于 \(i\le k\times sz\)，\(j\le k\)，我们可以将树上的每一个节点看成 \(k^2\) 个节点，每次转移等价于合并两个点；因此时间复杂度为 \(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
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
#include<iostream>
#define ll long long
using namespace std;
const int N = 1010;
const int K = 6;
const int MOD = 1e9 + 7;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, k;
int sz[N];
int f[N][N * K][K], g[N * K][K];

void dfs(int u, int fa) {
    sz[u] = 1;
    for(int i = 1; i <= k; i++) f[u][0][i] = 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs(v, u);
        for(int i = 0; i <= (sz[u] + sz[v]) * k; i++) {
            for(int j = 0; j <= k; j++) {
                g[i][j] = 0;
            }
        }
        for(int i = 0; i <= sz[u] * k; i++) {
            for(int j = 0; j <= k; j++) {
                if(!f[u][i][j]) continue;
                for(int p = 0; p <= sz[v] * k; p++) {
                    for(int q = 0; q <= k; q++) {
                        (g[i + p + q][max(0, j - q)] += (ll)f[u][i][j] * f[v][p][q] % MOD) %= MOD;
                    }
                }
            }
        }
        sz[u] += sz[v];
        for(int i = 0; i <= sz[u] * k; i++) {
            for(int j = 0; j <= k; j++) {
                f[u][i][j] = g[i][j];
            }
        }
    }
}

int ans[N * K];

int main() {

    cin >> n >> k;
    for(int i = 1, u, v; i <= n - 1; i++) {
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs(1, 0);

    for(int i = 0; i <= n * k; i++) {
        for(int j = 0; j <= k; j++) {
            (ans[i + j] += f[1][i][j]) %= MOD;
        }
    }

    for(int i = 1; i <= n * k; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}