题解 | 称砝码

#include <iostream>
using namespace std;

int w[110],a[110];
int f[2000010];
int main() {
    int n,num = 0;;cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>w[i];
        
    }
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        num = num+w[i]*a[i];
    }
    for(int i = 0;i<=a[0];i++){
        f[w[0]*i] = 1;
    }
    int cnt  = w[1]*a[1];
    for(int i = 1;i<=n;i++){//第几个砝码
        for(int j =1;j<=a[i];j++){//个数
            for(int k = cnt;k>=0;k--){
                // //为了防止新增重量不出现在当前基础堆的称重重量中导致加两次，需要倒序遍历当前基础堆的称重
                if(f[k]){
                    f[k+w[i]] = 1;
                }
            }
            cnt += w[i];
        }
    }
    int sum = 0;
    for(int i = 0;i<=2000010;i++){
        if(f[i]){
            sum++;
        }
    }
    cout<<sum<<'\n';

    return 0;
}
// 64 位输出请用 printf("%lld")

关键在于防止新增重量不出现在当前基础堆的称重重量中导致加两次，需要倒序遍历当前基础堆的称重，让其状态为1，计算总数即可

活动地址https://www.nowcoder.com/discuss/726480854079250432