C++动态规划set | #称砝码#

动规核心思想是上一次的状态决定下一次的状态，姑且算是吧。

因为需要使用每次循环结束时的状态，而循环中的状态时刻在变，所以set需要一个副本记录上一次循环结束时的状态。

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

int diffW(vector<int> w){
    unordered_set<int> res;
    for(int i = 0; i < w.size(); i ++){
        unordered_set<int> new_set = res;

        res.insert(w[i]);
        for(auto j : new_set) res.insert(j + w[i]);
    }

    return res.size() + 1; //考虑没有砝码的情况
}


int main() {
    int N;
    cin >> N;
    vector<int> weight(N);
    for(int i = 0; i < N; i ++){
        cin >> weight[i];
    }
    vector<int> num(N);
    for(int i = 0; i < N; i ++){
        cin >> num[i];
    }

    vector<int> w;
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < num[i]; j ++) w.push_back(weight[i]);
    }

    cout << diffW(w) << endl;

    return 0;
}
// 64 位输出请用 printf("%lld")