每日一道算法题 称砝码

题目

称砝码_牛客题霸_牛客网 (nowcoder.com)

Python

n=int(input())
weight=list(map(int,input().split()))
count=list(map(int,input().split()))

w_li=[]
for _ in range(n):
    for i in range(count[_]):
        w_li.append(weight[_])

ans={0}
for w in w_li:
    tmp={w+a for a in ans}
    ans.update(tmp)
print(len(ans))

C++

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

int main() {
    int n;
    cin >> n; 
    vector<int> weight(n);
    vector<int> count(n);
    for (int i = 0; i < n; i++) 
        cin >> weight[i];
    for (int i = 0; i < n; i++) 
        cin >> count[i];
    set<int> ans; 
    ans.insert(0); 
    for (int i = 0; i < n; i++)
     { 
        for (int j = 1; j <= count[i]; j++) 
        { 
            set<int> tmp(ans);  //创建ans的副本
            for (auto iter = tmp.begin(); iter != tmp.end();
                    iter++) 
                ans.insert(*iter + weight[i]);
        }
    }
    cout << ans.size() << endl; 
    return 0;
}

C语言