[ABC321F] #(subset sum = K) with Add and Erase

Genius_Star · 2023-09-24 16:17:56 · 题解

题意：

有一个箱子，每次可以向里面添加或拿走一个数，问每次操作后，任选箱子里的数加在一起，和等于 k 的方法数是多少？

思路：

可惜赛时没开 F，真的很简单……

注意到 q 和 k 都很小，只有 5000，说明 O(q \times k) 可过。

因为涉及到计数问题，考虑动态规划，定义 dp_i 为和等于 i 的方案数，初始状态为 dp_0=1。

对于每次添加的数，状态转移方程为 i \ge x,dp_i \to dp_i + dp_{i-x}，就是说 i 的方案数可以从 i-x 转移过来（因为可以加上 x），而且注意，要倒序枚举 i，正序的话方案数会多计算。

对于每次减去的数，状态转移方程为 i \ge x,dp_i \to dp_i - dp_{i-x}，就是说，在 i-x 这个数这里，没有 x 的话，是加不到 i 那里去的，所以要减去 dp_{i-x}（有重复的 x 也是一样的，只会将其中一个 x 的贡献减掉）。

对于每次询问之后，输出 dp_k 即可。

时间复杂度为：O(q \times k)。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5050,mod=998244353;
ll read(){
    ll x;
    scanf("%lld",&x);
    return x;
}
void write(ll x){
    printf("%lld",x);
}
char op;
ll q,x,k;
ll dp[N];
int main(){
    q=read(),k=read();
    dp[0]=1;
    while(q--){
        cin>>op;
        x=read();
        if(op=='+'){
            for(int i=k;i>=x;i--)
              dp[i]=(dp[i]+dp[i-x])%mod;
        } 
        else if(op=='-'){
            for(int i=x;i<=k;i++)
              dp[i]=(dp[i]-dp[i-x]+mod)%mod;
        }
        write(dp[k]);
        putchar('\n');
    }
    return 0;
}