题解 | #称砝码#

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        vector<int> weight(n);
        vector<int> num(n);
        int sum = 0;
        for (int i = 0; i < n; i++) //输入n种砝码重量
            cin >> weight[i];
        for (int i = 0; i < n; i++) { //输入n种砝码的数量
            cin >> num[i];
            sum += num[i] * weight[i]; //砝码总重量
        }
        vector<bool> dp(sum + 1, false); //记录0到sum是否可行
        dp[0] = true;
        for (int i = 0; i < n; i++) { //遍历每一种砝码
            for (int j = 0; j < num[i]; j++) { //遍历砝码每一个数量
                for (int k = sum; k >= weight[i]; k--) //每次剩余的每个都可以添加
                    if (dp[k - weight[i]])
                        dp[k] = 1;
            }
        }
        int count = 0;
        for (int i = 0; i <= sum;
                i++) //找到为1的就是可以组成的质量，计数
            if (dp[i])
                count++;
        cout << count << endl;
    }
    return 0;
}