题目描述

难度分:$1645$

输入$q(1 \leq n \leq 5000)$和$k(1 \leq k \leq 5000)$。一开始有一个空箱子。输入$q$个操作：

1. + v：把一个写有数字$v$的小球放入箱子。
2. - v：从箱子中移除一个写有数字$v$的小球，保证箱子中有这样的小球。

$v$的范围是$[1,5000]$。每次操作后，输出有多少种方案，从箱子中选取一些球，元素和恰好等于$k$。答案模$998244353$。注意球是有区分的。

输入样例

15 10
+ 5
+ 2
+ 3
- 2
+ 5
+ 10
- 3
+ 1
+ 3
+ 3
- 5
+ 1
+ 7
+ 4
- 3

输出样例

0
0
1
0
1
2
2
2
2
2
1
3
5
8
5

算法

背包撤销

这个套路要对01背包有比较深刻的理解才能想得比较清楚，不然就是见过就会没见过就不会系列。

初始化$dp[0]=1$，表示一个数字都不选有一种方案。如果没有删除操作的话，每次加入一个$v$，就从$k$到$v$（倒序）做一次01背包，状态转移方程为$dp[i]=dp[i]+dp[i-v]$。

而删除数字$v$，其实就是撤销之前加数字的转移，从$v$到$k$（正序）做一次01背包，状态转移方程为$dp[i]=dp[i]-dp[i-v]$。

解释一下为什么撤销是对的？可以这样理解，物品顺序不影响$dp$值的计算，那么当我取出数字$v$的时候，我可以把+ v调换到取出之前，也就是刚加进去就拿出来，这样之前写的$dp[i]=dp[i]+dp[i-v]$就可以立刻用$dp[i]=dp[i]-dp[i-v]$撤销掉，$dp$现在就变成了没有$v$的方案数。

复杂度分析

时间复杂度

对于每个操作，都要用$O(k)$的时间复杂度来进行背包求解。一共有$O(q)$个操作，所以时间复杂度为$O(qk)$。

空间复杂度

本质上就是个01背包问题，可以把物品索引那一维给优化掉，因此额外空间复杂度为$O(k)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 5010, MOD = 998244353;
int q, k, dp[N];

int main() {
    cin >> q >> k;
    memset(dp, 0, sizeof dp);
    dp[0] = 1;
    while(q--) {
        char c;
        int v;
        cin >> c >> v;
        if(c == '+') {
            for(int i = k; i >= v; i--) {
                dp[i] = (dp[i] + dp[i - v]) % MOD;
            }
        }else {
            for(int i = v; i <= k; i++) {
                dp[i] = (dp[i] - dp[i - v] + MOD) % MOD;
            }
        }
        printf("%d\n", dp[k]);
    }
    return 0;
}