「做题记录」背包 DP 选做
stripe_python · · 算法·理论
写一些背包的理论,然后做题。
经典问题
背包可以是最优化 DP,可以是计数 DP,也可以是可行性 DP。
约束变形
- 分组背包:每组分别跑背包。P1757。
- 多重背包:二进制拆分后转 01 背包。也有单调队列优化的做法。P1776。
- 混合背包:根据物品类型选择对应转移。P1833。
- 二维费用背包:状态设计记下所有类型的费用。P1855。
- 树形背包:在子树根
u 对每个儿子v 做卷积f_{u,i+j} \gets f_{u,i} +f_{v,j} 。需要卡上界i \le \min(V,sz_u), j \le \min(V-i,sz_v) ,则复杂度严格O(nV) 。P2014。- 更详细的讨论:https://loj.ac/d/3144。
答案变形
- 达成最优解的方案数:将 DP 记录的信息改为二元组
(a,b) ,分别为最优解和方案数,具有可加性。 - 前
k 优解:将 DP 记录的信息改为一个长为k 的序列,合并时归并一下并删去多余元素,复杂度O(nkV) 。P1858。 - 构造方案:DP 时记录上一个决策点,得到最优解后反向遍历并输出。
多次询问
- 背包合并:设背包为
f_i,g_i ,枚举两个体积i,j 做卷积f_i+g_j \to h_{i+j} 。常见于前后缀背包的合并。 - 区间询问背包:离线分治,做二区间合并,即从分治中点向两侧处理背包。复杂度
O(nV \log n+qV) 。P6240。 - 加物品删物品:离线分治,做线段树分治。只需考虑加物品,撤销直接复制原本的 DP 数组传入子树。CF601E。
可行性
对于可行性背包,我们可以用 bitset 优化到
考虑加入物品 f |= f << v。
删除物品
退背包
P4141 消失之物:
现有
n 个物品,体积为v_i ,价值为1 。对每个i=1,2,\cdots,n 求出:如果缺失了物品i ,装满背包的方案数,对10 取模。
朴素做法显然是
考虑加入 01 背包的转移
由于加入背包的物品顺序没有影响,我们就可以依次撤销每个物品,复杂度优化到
:::::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 并输出。
关键观察:至多存在一个数组没有被选满。证明这个结论并不是这里的主题,有兴趣的读者可以阅读另一篇题解。
因此我们可以枚举缺失哪个数组,然后做
现在引入缺一分治的观点。设当前分治区间为
- 将
[l,m] 中的物品加入,递归(m,r] ; - 将背包还原为进入
[l,r] 时的状态; - 将
(m,r] 中的物品加入,递归[l,m] 。
根据这个流程,当前区间为
加入物品是
缺一分治和线段树分治 & 二区间合并的思想是类似的。
:::::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 背包:构造背包数组
将体积为
加入物品
删除物品
完全背包:同理构造背包数组
物品
做卷积得到总 GF
加入物品 & 删除物品的推导类似,注意一下循环顺序即可,这里不推导了。
加速背包
下面我们以
首先取
代入
记
设体积上限为
算出右侧 GF 后一次多项式
01 背包的 GF 优化类似,不过在 Taylor 展开时会带一个调节符号
凸优化
推荐阅读。
简单来说,利用最优化背包的凸性,我们可以得到一个
练习
P10960 SUBSTRACT
给出一个长为
n 的序列a_i 。第i 次操作选择一个x ,令a_x \gets a_x-a_{x+1} 并删去a_{x+1} 。目标为n-1 次操作后序列恰好剩下一个数k 。输出构造,数据保证有解。
:::::success[题解]
不难发现,最终的
那么转化为构造一组权值
这就是个很经典的 01 背包了,物品价值是
根据
| bitset 优化可行性背包,复杂度 |
|---|
:::::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:记
我们需要发现性质,然后用贪心优化 DP。
考虑如下情景:我们已经确定了最优解中选择哪些元素。这种情况下有一个贪心:我们按
对于前面的元素,我们一定是尽量使用优惠券直到买满。那么整个场面上至多有一个元素没有被买满,是使用钱 + 优惠券混用得到的。
拓展到一般情况,将元素按
我们可以对前缀做一个
| 复杂度 |
|---|
:::::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 个。每种球的限制为:
- 偶数个;
- 奇数个;
- 不超过一个;
求选择的方案数,对
10007 取模。
:::::success[题解]
这是一个混合背包问题。根据 GF 知识,写出
于是答案的 GF
由广义二项式定理展开得
| 答案即 |
|---|
:::::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[题解]
不妨设根节点的颜色为
- 当
m>2 时,容易构造所有边端点颜色不同的情况,比如按深度对m-1 取模染色。 - 当
m=2 时,森林中所有边都有贡献。
据此设计树形 DP:
其中
注意合并 DP 时需要新建数组,不然会覆盖原本的取值。无解容易判断。
| 正确的实现为树形背包复杂度,复杂度 |
|---|
:::::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 的规则,访问
注意到总的 DFS 序数目为
对于祖先节点
我们需要知道子树大小总和为
分析向
| 得到以上信息后,将 |
|---|
:::::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';
}
}
:::::