题解 | #最小覆盖子串#

• 技巧在于：每遍历一种砝码，都在上一轮所有砝码的集合中迭代

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


int main() {
    int n; // 种类
    vector<int> weights; // 重量
    vector<int> cnt; // 数量
    while(cin >> n) {
        weights.resize(n);
        cnt.resize(n);
        for(int i = 0; i < n; i++) {
            cin >> weights[i];
        }
        for(int i = 0; i < n; i++) {
            cin >> cnt[i];
        }
        
        unordered_set<int> ans;
        ans.insert(0);
        for(int i = 0; i < n; i++) { // 每一种砝码
            for(int j = 1; j <= cnt[i]; j++) { // 用完之前数量之前
                unordered_set<int> temp(ans);
                for(auto iter = temp.begin(); iter != temp.end(); iter++){
                    ans.insert(*iter + weights[i]);
                }
            }
        }

        cout << ans.size() << endl;
    }
}