本题需要注意的点包括,每一种新的种类需要和之前的所有可能的重量相加。因此可以直接在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; }