题解 | #称砝码#

#include <iostream>
#include <string>
#include <stdio.h>
#include <set>
#include <string.h>
#include <algorithm>
#include <map>
#include <iterator>
#include <vector>
#include <ctype.h>
#include <array>
#include <numeric>

using namespace std;

void add_goods_in_vector(vector<int> &goods, int goods_max_num, int weight_per_goods)
{
    int current = 1;
    while (goods_max_num > 0)
    {
        if (goods_max_num >= current)
        {
            goods.push_back(current * weight_per_goods);
            goods_max_num -= current;
            current = current * 2;
        }
        else
        {
            goods.push_back(goods_max_num * weight_per_goods);
            break;
        }
    }
}

int main(void)
{
#ifdef DEBUG_TEST_LYJ
    freopen("input.txt", "r", stdin);
#endif
    int goods_type;
    cin >> goods_type;
    vector<int> goods_weight(goods_type);
    for (int i = 0; i < goods_type; ++i)
    {
        cin >> goods_weight[i];
    }
    vector<int> goods_num(goods_type);
    for (int i = 0; i < goods_type; ++i)
    {
        cin >> goods_num[i];
    }
    int max_weight = 0;
    vector<int> goods_info;
    for (int i = 0; i < goods_type; ++i)
    {
        max_weight += goods_num[i] * goods_weight[i];
        add_goods_in_vector(goods_info, goods_num[i], goods_weight[i]);
    }

    vector<short> dp(max_weight + 1, 0);
    dp[0] = 1;
    for(int index = 0; index < goods_info.size(); ++index) {
        for(int target_weight = max_weight; target_weight >= goods_info[index] ; --target_weight) {
            if(dp[target_weight - goods_info[index]] == 1) {
                dp[target_weight] = 1;
            }
        }
    }

    int sum = accumulate(dp.begin(), dp.end(), 0);
    cout << sum << endl; 

    return 0;
}