跳转至

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)\),可以通过本题。

模板代码
#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" 的限制。

代码
#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)\)

代码
#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;
}