题解 | #称砝码#(C++ std::bitset DP)

春招刷题训练营 2025/3/12 困难组 称砝码

如果不考虑数量，那么这个问题实际上就是一个每个物品价值为1的01背包变种问题,得到重量，初始化，转移方程为，时间复杂度。对于数量问题，由于数量最大也只有10，所以我们可以直接给每个物品重复跑遍即可，时间复杂度。如果数量上限更大的话，则需使用多重背包的二进制优化。在实现方面，可以使用优化到。

#include <iostream>
#include <bitset>
#include <vector>

int main(){
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for(int i = 1;i <= n;i++){
        std::cin >> a[i];
    }
    std::bitset<200010> b; 
    for(int i = 1;i <= n;i++){
        int x;
        std::cin >> x;
        for(int j = 0;j < x;j++){
            b[0] = 1;
            b |= (b << a[i]);
        }
    }
    std::cout << b.count() << "\n";
    return 0;
}