本题需要注意的点包括,每一种新的种类需要和之前的所有可能的重量相加。因此可以直接在unordered_set<int>中进行操作,一方面可以直接实现去重,另一方面可以实现对每个重量进行叠加。
#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;
int main(){
int n = 0;
cin >> n;
vector<int> m;
vector<int> x;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < n; j++) {
int temp = 0;
cin >> temp;
if (i == 0) m.push_back(temp);
if (i == 1) x.push_back(temp);
}
}
unordered_set<int> res;
res.insert(0);
for (int i = 0; i < n; i++) {
int mi = m[i];
int xi = x[i];
for (int j = 0; j < xi; j++) {
unordered_set<int> temp(res);
for (unordered_set<int>::iterator iter = temp.begin(); iter != temp.end(); iter++) {
int val = mi + *iter;
if (res.find(val) == res.end()) res.insert(val);
}
}
}
cout << res.size() << endl;
}

京公网安备 11010502036488号