题解：ABC321F - #(subset sum = K) with Add and Erase

题解：ABC321F - #(subset sum = K) with Add and Erase

·题目

链接：Atcoder。

链接：洛谷。

·难度

算法难度：B。

思维难度：C。

调码难度：B。

综合评价：见洛谷链接。

·算法

动态规划。

·思路

状态：f[i]表示目前为止能使得和为i的取法总数。

初值：f[0]肯定是1。

转移：若是“+”操作，这样转移：

for(long long j=5000;j>=x;j--){
    f[j]=(f[j]+f[j-x]+p)%p;
}

每个状态f[j]需要添加原来状态的f[j-x]，以此模拟在每个取法的基础上增加一个“x”。

注意，这里是倒着遍历，否则会出现一个值在一个取法中被添加多次，类似于01背包和完全背包的转移区别。

若是“-”操作，这样转移：

for(long long j=x;j<=5000;j++){
    f[j]=(f[j]-f[j-x]+p)%p;
}

每个状态f[j]需要删除目前状态的f[j-x]，以此模拟在每个取法的基础上删除一个“x”。

注意，这里是正着遍历，否则会出现一个值在一个取法中被删除多次，类似于上面的函数反过来。

·代价

O(q*max(x))。这里max(x)当成5000算即可。

·细节

字符输入用string。

·代码

#include
#define K 5500
using namespace std;
const long long p=998244353;
long long f[K]={},k=0,q=0;
//状态：f[i]表示目前为止使得和为i的方案书
int main(){
    scanf("%lld%lld",&q,&k);
    f[0]=1;
    //初始值：和为0就是啥也不选
    for(long long i=1;i<=q;i++){
        string str="";
        cin>>str;
        long long x=0;
        scanf("%lld",&x);
        if(str=="+"){
            for(long long j=5000;j>=x;j--){
                f[j]=(f[j]+f[j-x]+p)%p;
            }
            //转移：每个状态f[j]在原基础上加上转移前（避免出现一个数被多次添加的情况）的f[j-x]，表示选择该物品的情况
        }else{
            for(long long j=x;j<=5000;j++){
                f[j]=(f[j]-f[j-x]+p)%p;
            }
            //转移：每个状态f[j]在原基础上减去转移后（避免出现一个数被多次删除的情况）的f[j-x]，表示丢弃该物品的情况
        }
        printf("%lld\n",f[k]);
        //输出结果
    }
    return 0;
}

·注意

遍历顺序不要反。