可撤销背包学习笔记
Nicrobot
·
·
个人记录
发现这么简单的东西不会。
更新中。
简介
可撤销背包用于解决如下问题：给定大小为 m 的背包，支持插入、删除任意物品，查询使得背包容量为 k 的方案数。
插入就是普通的背包。
删除 w_i 重量的物品时，令 dp_i 减去 dp_{i-w_i} 即可。
注意，枚举的顺序应该与原来的顺序相反。
直接上例题：
例 1 [ABC321F] #(subset sum = K) with Add and Erase
给定大小为 k 的背包和 q 次操作，支持两种操作：
- 插入一个大小为 x 的元素；
- 删除一个大小为 x 的元素。
每次操作后，求装满背包方案数。
----
板子。贴个代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int mod = 998244353;
int Q, k, dp[N];
void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
int main() {
cin >> Q >> k;
dp[0] = 1;
while (Q--) {
char op; int x;
cin >> op >> x;
if (op == '+') {
for (int j = k; j >= x; j--) {
add(dp[j], dp[j - x]);
}
} else {
for (int j = x; j <= k; j++) {
add(dp[j], -dp[j - x]);
}
}
cout << dp[k] << '\n';
}
return 0;
}
```
### 例 2：P4141 消失之物
有 $n$ 个物品和大小为 $m$ 的背包，物品有价格 $w_i$ 对于每个物品 $i\in[1,n]$，容量 $j\in[1,m]$，求除了 $i$ 的所有物品中，选择物品使得物品容量总和为 $j$ 的方案数 $\bmod \ 10$ 的值。
$1\le n,m,w_i\le 2\ 000$。
---
先做完 01 背包，再对于每个物品删除它，求出答案，再把它加回去就行了。