题解 | #称砝码#

#include<bits/stdc++.h>
using namespace std;

void dfs(unordered_set<int>& res,vector<int>& m, vector<int> used,int index,int sum)
{
    if(index == used.size())
    {
        res.insert(sum);
        return;
    }
    for(int i = index; i < used.size(); i++)
    {
        for(int j = 0; j <= used[i]; j++)
        {
            used[i] -= j;
            dfs(res,m,used,index+1,sum+j*m[i]);
            used[i] += j;
        }
    }
    
}

int main()
{
    //1.先处理输入吧
    int n ;
    cin >> n;
    vector<int> m(n);
    vector<int> x(n);
    for(int i = 0; i < n; i++)
    {
        cin >> m[i];
    }
    for(int i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    //2.debug查看输入数据是否准确保存
//     for(int i = 0; i < n; i++)
//     {
//         cout << m[i] << " ";
//     }
//     cout << endl;
//     for(int i = 0; i < n; i++)
//     {
//         cout << x[i] << " ";
//     }
    //3.计算可以称出来的不同的重量数
//     int count = 1;//初始值为1是因为称重量包括0
    unordered_set<int> res;
    res.insert(0);
//     vector<int> used = x;
    //dfs(res,m,used,0,0);
    unordered_set<int>::iterator it;
    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= x[i]; j++ )
        {
            unordered_set<int> temp(res);
            for(it = temp.begin(); it != temp.end(); it++ )
            {
                res.insert(*it + m[i]);
            }
        }
    }
    //4.处理输出
    cout << res.size() << endl;
    
    
    return 0;
}

备注：dfs会超时