「做题记录」背包 DP 选做

· · 算法·理论

写一些背包的理论,然后做题。

经典问题

背包可以是最优化 DP,可以是计数 DP,也可以是可行性 DP。

约束变形

答案变形

多次询问

可行性

对于可行性背包,我们可以用 bitset 优化到 O\left(\dfrac{nV}{w}\right)。

考虑加入物品 v 的可行性背包,则转移为 f_i \gets f_{i-v}。如果将 f 开成 bitset,写到代码里就是 f |= f << v。

删除物品

退背包

P4141 消失之物:

现有 n 个物品,体积为 v_i,价值为 1。对每个 i=1,2,\cdots,n 求出:如果缺失了物品 i,装满背包的方案数,对 10 取模。

朴素做法显然是 O(n^2 V) 的,无法通过。

考虑加入 01 背包的转移 f_i \gets f_i+ f_{i-v},我们可以做这个过程的逆操作。我们正序枚举 i,并且做 f_ i\gets f_i-f_{i-v}。

由于加入背包的物品顺序没有影响,我们就可以依次撤销每个物品,复杂度优化到 O(nV)。这个 trick 叫做退背包,它只适用于求方案数的背包。

:::::info[代码]

const int N = 2005;
int n, m, v[N];
mint f[N], g[N];

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i];
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) f[j] += f[j - v[i]];
    }
    for (int i = 1; i <= n; i++) {
        copy(f, f + m + 1, g);
        for (int j = v[i]; j <= m; j++) g[j] -= g[j - v[i]];
        for (int j = 1; j <= m; j++) cout << g[j];
        cout << '\n';
    }
}

:::::

缺一分治

缺一分治可以解决的问题和退背包是类似的,但是缺一分治可以做最优化的背包。

CF1442D Sum:

给定 n 个不降数组 a_i。你初始持有一个 x=0,进行 k 次操作:选择一个数组,将 x 加上数组的第一个元素,然后删去该元素。最大化最终的 x 并输出。

关键观察:至多存在一个数组没有被选满。证明这个结论并不是这里的主题,有兴趣的读者可以阅读另一篇题解。

因此我们可以枚举缺失哪个数组,然后做 \max 背包,复杂度 O(n^2 k)。

现在引入缺一分治的观点。设当前分治区间为 [l,r],中点为 m,进行如下算法流程:

  1. 将 [l,m] 中的物品加入,递归 (m,r];
  2. 将背包还原为进入 [l,r] 时的状态;
  3. 将 (m,r] 中的物品加入,递归 [l,m]。

根据这个流程,当前区间为 [l,r] 时背包中的物品恰为 [1,l) \cup (r,n]。因此我们在 l=r 时统计答案。

加入物品是 O(k) 的,由递归式 T(n)=2T\left(\dfrac{n}{2}\right)+O(nk) 解得 T(n)=O(nk \log n)。

缺一分治和线段树分治 & 二区间合并的思想是类似的。

:::::info[代码]

const int N = 3005;
int n, k, v[N];
i64 ans, w[N];
vector<i64> a[N];

void solve(int l, int r, vector<i64>& f) {
    if (l == r) {
        for (int i = 0; i <= min(k, v[l]); i++) chmax(ans, f[k - i] + a[l][i]);
        return;
    }
    int mid = (l + r) >> 1;
    vector<i64> g(f.begin(), f.end());
    for (int i = l; i <= mid; i++) {
        for (int j = k; j >= v[i]; j--) chmax(f[j], f[j - v[i]] + w[i]);
    }
    solve(mid + 1, r, f);
    copy(g.begin(), g.end(), f.begin());
    for (int i = mid + 1; i <= r; i++) {
        for (int j = k; j >= v[i]; j--) chmax(f[j], f[j - v[i]] + w[i]);
    }
    solve(l, mid, f);
}

void _main() {
    cin >> n >> k;
    for (int i = 1, x; i <= n; i++) {
        cin >> x, v[i] = x, a[i] = {0};
        for (int v; x--; ) {
            cin >> v, w[i] += v;
            if (a[i].empty()) a[i].emplace_back(v);
            else a[i].emplace_back(a[i].back() + v);
        }
    }
    vector<i64> f(k + 1);
    solve(1, n, f), cout << ans;
}

:::::

GF 观点

我们用 GF 观点来看待求方案数的背包问题。

01 背包:构造背包数组 f_i 的 GF

F(x)=\sum_{i=0}^n f_i x^i

将体积为 v 的物品视为 F_v(x)=1+x^v。1 表示不选,x^v 表示选。如果有 n 个物品 v_i,则背包结果即所有物品 GF 的卷积

F(x) = \prod_{i=1}^n (1+x^{v_i})

加入物品 v 即做卷积 F(x)=F_0(x) \times (1+x^v),提取系数得 [x^k] F(x)=[x^k] F_0(x)+[x^{k-v}] F_0(x)。体现在代码中就是倒序遍历 k 做加法。

删除物品 v 则为多项式除法 F(x)=\dfrac{F_0(x)}{1+x^v}。移项然后对比系数 [x^k] F(x)=[x^k] F_0(x)-[x^{k-v}] F(x)。这也就是我们上面的退背包,正序遍历 k 做减法。

完全背包:同理构造背包数组 f_i 的 GF

F(x)=\sum_{i=0}^n f_i x^i

物品 v 有无数个,因此单物品 GF 为

F_v(x)=\prod_{i=0}^{\infty} x^{iv}=\dfrac{1}{1-x^v}

做卷积得到总 GF

F(x) = \prod_{i=1}^n \dfrac{1}{1-x^{v_i}}

加入物品 & 删除物品的推导类似,注意一下循环顺序即可,这里不推导了。

加速背包

下面我们以 F(x) = \prod\limits_{i=1}^n \dfrac{1}{1-x^{v_i}} 为例,讲一下 poly 科技怎么优化这个东西。板子题 P4389 付公主的背包。

首先取 \ln 化乘为加:

\begin{aligned} F(x) &= \prod\limits_{i=1}^n \dfrac{1}{1-x^{v_i}}\\ \ln F(x) &= \ln \prod\limits_{i=1}^n \dfrac{1}{1-x^{v_i}}\\ \ln F(x) &= -\sum_{i=1}^n \ln (1-x^{v_i}) \end{aligned}

代入 \ln(1-x) 的 Taylor 展开

\begin{aligned} \ln F(x) &= -\sum_{i=1}^n \ln (1-x^{v_i})\\ \ln F(x) &= \sum_{i=1}^n \sum_{j=1}^{\infty} \dfrac{x^{j \times v_i}}{j} \end{aligned}

记 c_i 为体积为 i 的物品数,合并同类项

\begin{aligned} \ln F(x) &= \sum_{i=1}^n \sum_{j=1}^{\infty} \dfrac{x^{j \times v_i}}{j}\\ \ln F(x) &= \sum_{v} c_v \sum_{j=1}^{\infty} \dfrac{x^{jv}}{j} \end{aligned}

设体积上限为 V,第一个循环的上界为 V,第二个循环的上界为 \dfrac{V}{v}。直接枚举 v,j 计算右侧,复杂度为调和级数 O(V \log V)。

算出右侧 GF 后一次多项式 \exp 即可,总复杂度 O(V \log V)。代码没写。

01 背包的 GF 优化类似,不过在 Taylor 展开时会带一个调节符号 (-1)^{j-1}。

凸优化

推荐阅读。

简单来说,利用最优化背包的凸性,我们可以得到一个 O(n \log n+ mV \log V) 的 01 背包,其中 m 是体积的种类数。在 m 远小于 n 时有很大的优势。

练习

P10960 SUBSTRACT

给出一个长为 n 的序列 a_i。第 i 次操作选择一个 x,令 a_x \gets a_x-a_{x+1} 并删去 a_{x+1}。目标为 n-1 次操作后序列恰好剩下一个数 k。输出构造,数据保证有解。

:::::success[题解] 不难发现,最终的 k 由 n 个数合并而来,且 a_1,a_2 的符号恒定,a_3 \sim a_n 的符号可以任意调节。

那么转化为构造一组权值 w_i \in \{-1,1\},使得 a_1-a_2+\sum \limits_{i=3}^n a_iw_i=k。移项以后两边同加 \sum \limits_{i=3}^n a_i,式子变成

\sum_{i=3}^n a_i(w_i+1)=k-a_1+a_2+\sum_{i=3}^n a_i

这就是个很经典的 01 背包了,物品价值是 2a_i,只有选和不选两种决策。用一个可行性 DP 做背包,然后倒推回去就能求得一组 w_i。

根据 w_i 的取值容易构造最终方案。具体地,我们先处理 w_i=1 的数字,依次从前往后操作 a_i,然后用一个操作 1 修正符号,接着不断进行操作 1 即可处理 w_i=-1 的数字。

bitset 优化可行性背包,复杂度 O(\frac{nV}{w})。

:::::info[代码]

const int N = 105, M = 2e4 + 5;
int n, k, a[N], w[N];
bitset<M> f[N];

void _main() {
    cin >> n >> k;
    if (n == 1) return;
    if (n == 2) return cout << 1, void();
    for (int i = 1; i <= n; i++) cin >> a[i];
    int m = k - a[1] + a[2] + accumulate(a + 3, a + n + 1, 0);
    f[2][0] = 1;
    for (int i = 3; i <= n; i++) f[i] = f[i - 1] | (f[i - 1] << (2 * a[i]));
    for (int i = n, j = m; i >= 3; i--) {
        if (j >= 2 * a[i] && f[i - 1][j - 2 * a[i]]) w[i] = 1, j -= 2 * a[i];
        else w[i] = -1;
    }
    int cnt = 0;
    for (int i = 2; i <= n; i++) if (w[i] == 1) 
        cout << i - cnt - 1 << '\n', cnt++;
    cout << 1 << '\n';
    for (int i = 2; i <= n; i++) if (w[i] == -1)
        cout << 1 << '\n';
} 

:::::

P8903 [USACO22DEC] Bribing Friends G

现有 n 个元素 (p_i,c_i,x_i)。你初始持有 a 元钱和 b 张优惠券。对于第 i 个元素,你可以支付 c_i 元获得 p_i 的得分。同时,如果你支付 x_i 张优惠劵,你还可以获得 1 元的折扣,折扣的上限为 c_i。最大化得分并输出。

:::::success[题解] 容易设计一个 DP:记 f_{i,j,k} 为考虑到第 i 个元素,当前持有 j 元钱,k 张优惠券,枚举对第 i 个元素支付的优惠券可以转移。视 n,V 同阶复杂度 O(n^4),无法通过。

我们需要发现性质,然后用贪心优化 DP。

考虑如下情景:我们已经确定了最优解中选择哪些元素。这种情况下有一个贪心:我们按 x_i 升序排序,并且顺次使用优惠券。

对于前面的元素,我们一定是尽量使用优惠券直到买满。那么整个场面上至多有一个元素没有被买满,是使用钱 + 优惠券混用得到的。

拓展到一般情况,将元素按 x_i 升序排序后,最优解一定形如:

我们可以对前缀做一个 (p_i,x_i) 的 01 背包,对后缀做一个 (p_i,c_i) 的 01 背包。在计算答案时,只需枚举中点,再枚举中点元素使用的优惠券数目,即用 (\max,+) 卷积合并前后缀背包。

复杂度 O(n^2),有一些 corner case。

:::::info[代码]

const int N = 2005;
int n, a, b, f[N][N], g[N][N];
struct node {
    int p, c, x;
} c[N];

void _main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) cin >> c[i].p >> c[i].c >> c[i].x;
    sort(c + 1, c + n + 1, [](const node& a, const node& b) -> bool {
        return a.x < b.x;
    });
    for (int i = 1; i <= n; i++) {
        int w = c[i].c * c[i].x;
        for (int j = 0; j <= b; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= w) f[i][j] = max(f[i][j], f[i - 1][j - w] + c[i].p);
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= a; j++) {
            g[i][j] = g[i + 1][j];
            if (j >= c[i].c) g[i][j] = max(g[i][j], g[i + 1][j - c[i].c] + c[i].p);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= c[i].c; j++) {
            if (j * c[i].x > b || c[i].c - j > a) continue;
            res = max(res, f[i - 1][b - j * c[i].x] + g[i + 1][a - c[i].c + j] + c[i].p);
        }
    } cout << res;
} 

:::::

BZOJ3028 食物

有 8 种不同颜色的无标号球,你总共需要选出 n 个。每种球的限制为:

  1. 偶数个;
  2. 奇数个;
  3. 不超过一个;

求选择的方案数,对 10007 取模。

:::::success[题解] 这是一个混合背包问题。根据 GF 知识,写出 8 个 GF 然后做卷积就是答案 GF。依次为:

F_1(x)=\sum_{i}x^{2i}=\dfrac{1}{1-x^2} F_2(x)=1+x F_3(x)=1+x+x^2 F_4(x)=\sum_{i}x^{2i+1}=\dfrac{x}{1-x^2} F_5(x)=\sum_{i}x^{4i}=\dfrac{1}{1-x^4} F_6(x)=1+x+x^2+x^3 F_7(x)=1+x F_8(x)=\sum_{i}x^{3i}=\dfrac{1}{1-x^3}

于是答案的 GF

F(x)=\dfrac{x(1+x)^2(1+x+x^2)(1+x+x^2+x^3)}{(1-x^2)(1-x^3)(1-x^4)}=\dfrac{x}{(1-x)^4}

由广义二项式定理展开得

F(x)=\sum_i \binom{i+2}{i-1} x^i
答案即 [x^n] F(x)=\binom{n+2}{3}=\frac{n(n+1)(n+2)}{6},读入时取模即可。

:::::info[代码]

mint n;
char c;
void _main() {
    while (cin >> c) n = n * 10 + (c ^ 48);
    cout << n * (n + 1) * (n + 2) / 6;
}

:::::

P4362 [NOI2002] 贪吃的九头龙

给出一棵节点数为 n 的有根树,根节点为 1,边带权。你需要将这棵树 m 染色,满足与根节点同色的节点数恰为 k。代价为两端点颜色相同的边的边权和,最小化代价并输出,或报告无解。

:::::success[题解] 不妨设根节点的颜色为 1。我们钦定 k 个节点的颜色为 1,则剩余点形成一个森林,需要 m-1 染色。

据此设计树形 DP:f_{0/1,u,i} 表示考虑 u 的子树,u 节点染色是否染成 1,子树内选择 i 个染成 1 的最小代价。枚举儿子 v 并合并 DP 数组,转移是 (\min,+) 卷积:

f_{0/1,u,i+j} \gets f_{0/1,u,i}+f_{0/1,v,j}+w

其中 w 为转移时 u \to v 的边是否产生贡献,容易根据 m 是否等于 2 以及 0/1 维的取值计算。

注意合并 DP 时需要新建数组,不然会覆盖原本的取值。无解容易判断。

正确的实现为树形背包复杂度,复杂度 O(n^2)。

:::::info[代码]

const int N = 305, inf = 0x3f3f3f3f;
int n, m, k;
vector<pair<int, int>> e[N];

int sz[N], f[2][N][N];
void dfs(int u, int fa) {
    f[0][u][0] = 0, f[1][u][1] = 0, sz[u] = 1;
    for (auto [v, w] : e[u]) {
        if (v == fa) continue;
        dfs(v, u);
        vector<int> f0(N, inf), f1(N, inf);
        for (int i = min(sz[u], k); i >= 0; i--) {
            for (int j = min(sz[v], k - i); j >= 0; j--) {
                chkmin(f0[i + j], f[0][u][i] + f[0][v][j] + (m == 2) * w);
                chkmin(f0[i + j], f[0][u][i] + f[1][v][j]);
                chkmin(f1[i + j], f[1][u][i] + f[0][v][j]);
                chkmin(f1[i + j], f[1][u][i] + f[1][v][j] + w);
            }
        }
        sz[u] += sz[v];
        copy(f0.begin(), f0.end(), f[0][u]), copy(f1.begin(), f1.end(), f[1][u]);
    }
}

void _main() {
    cin >> n >> m >> k;
    if (n - k < m - 1) return cout << -1, void();
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
    } 
    memset(f, 0x3f, sizeof(f)), dfs(1, -1);
    cout << f[1][1][k];
} 

:::::

P9669 [ICPC 2022 Jinan R] DFS Order 2

给出一棵节点数为 n 的有根树,根节点为 1。对于每个 x=1,2,\cdots,n 和 p=1,2,\cdots,n 求出:在所有 DFS 序中,x 位于 DFS 序第 p 位的方案数。对 998244353 取模。

:::::success[题解] 根据 DFS 的规则,访问 x 之前必然访问了 x 的所有祖先和排在 x 之前的兄弟子树。

注意到总的 DFS 序数目为 \prod\limits_{u=1}^n |\operatorname{son}(u)|!,其中 \operatorname{son}(u) 是 u 的儿子集合。因此考虑计数转概率,计算 x 位于 DFS 序第 p 位的概率。

对于祖先节点 u,我们希望走向其儿子 v,并通向 x 的方向。记 m=|\operatorname{son}(u)|,则我们选出 i 个放在 v 前面,剩下 m-i-1 个放在后面。选出这种方案的概率系数为 \frac{i!(m-i-1)!}{m!}。

我们需要知道子树大小总和为 k 的情况数。记 f_{u,i,j} 为在 u 的 m 个儿子中选出 i 个儿子且子树大小之和恰为 j 的方案数。依次考虑儿子 v 然后用 01 背包合并:f_{u,i,j} \gets f_{v,i-1,j-sz_v}。

分析向 v 的路径时,我们不能算入 v 自身的方案。因此使用退背包,算出不含 v 的背包数组 g_{u,i,j},复杂度 O(n^3)。

得到以上信息后,将 g 与对应概率相乘并求和,得到总概率,答案容易计算。

:::::info[代码]

const int N = 505;
int n, sz[N], dep[N];
vector<int> e[N];
mint fac[N], ifac[N], h[N][N], ans[N][N];

void dfs1(int u, int fa) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == fa) continue;
        dep[v] = dep[u] + 1, dfs1(v, u), sz[u] += sz[v];
    }
}
void dfs2(int u, int fa) {
    if (e[u].size() == 1 && e[u][0] == fa) return;
    int m = u == 1 ? e[u].size() : e[u].size() - 1;
    vector<vector<mint>> f(m + 5, vector<mint>(sz[u] + 5));
    f[0][0] = 1;
    int sum = 0;
    for (int v : e[u]) {
        if (v == fa) continue;
        sum += sz[v];
        for (int i = m; i >= 1; i--) {
            for (int j = sum; j >= sz[v]; j--) f[i][j] += f[i - 1][j - sz[v]];
        }
    }
    for (int v : e[u]) {
        if (v == fa) continue;
        auto g = f;
        for (int i = 1; i <= m; i++) {
            for (int j = sz[v]; j <= sum; j++) g[i][j] -= g[i - 1][j - sz[v]];
        }
        vector<mint> p(sum + 5);
        for (int j = 0; j <= sum - sz[v]; j++) {
            for (int i = 0; i < m; i++) p[j] += g[i][j] * fac[i] * fac[m - i - 1] * ifac[m];
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= sum - sz[v] && i + j <= n; j++) h[v][i + j] += h[u][i] * p[j];
        }
        dfs2(v, u);
    }
}

void _main() {
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i];
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    h[1][0] = 1, dfs1(1, -1), dfs2(1, -1);
    mint t = fac[e[1].size()];
    for (int i = 2; i <= n; i++) t *= fac[e[i].size() - 1];
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i <= n; i++) {
            int pos = 1 + dep[u] + i;
            if (pos <= n) ans[u][pos] += h[u][i] * t; 
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << ans[i][j] << ' ';
        cout << '\n';
    }
} 

:::::