题解 | #称砝码#
称砝码
https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c
// HJ41-3 称砝码.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 #include<iostream> #include<bits/stdc++.h> using namespace std; int main() { int n; while (cin >> n) { vector<int>weight(n); vector<int>num(n); int sum = 0; for (int i = 0; i < n; i++) { cin >> weight[i]; } for (int i = 0; i < n; i++) { cin >> num[i]; sum += weight[i] * num[i]; } vector<int>flag(sum + 1, 0); flag[0] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < num[i]; j++) { for (int k = sum; k >= weight[i]; k--) { if (flag[k - weight[i]]) { flag[k] = 1; } } } } int count = 0; for (auto c : flag) { if (c) { count++; } } cout << count << endl; } return 0; }