题解 | 称砝码

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int main() {
    int n;
    cin >> n; // 输入砝码的个数

    vector<int> m(n); // 砝码的重量
    vector<int> x(n); // 砝码的数量

    // 输入砝码的重量
    for (int i = 0; i < n; ++i) {
        cin >> m[i];
    }

    // 输入砝码的数量
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }

    // 动态规划数组
    unordered_set<int> dp;
    dp.insert(0); // 初始状态：重量为 0

    // 遍历每种砝码
    for (int i = 0; i < n; ++i) {
        int weight = m[i]; // 当前砝码的重量
        int count = x[i];  // 当前砝码的数量

        // 复制当前的 dp 集合
        unordered_set<int> temp = dp;

        // 遍历当前 dp 集合中的每个重量
        for (int w : temp) {
            // 遍历当前砝码的数量
            for (int j = 1; j <= count; ++j) {
                int newWeight = w + j * weight; // 新重量
                dp.insert(newWeight); // 更新 dp 集合
            }
        }
    }

    // 输出可以称出的不同重量的数量
    cout << dp.size() << endl;

    return 0;
}

unordered_set相关：

（1）基于哈希表实现

• unordered_set 是 C++ 标准库中的一种容器，基于哈希表实现。
• 它的插入、查找和删除操作的平均时间复杂度为 O(1)。

（2）唯一性

• unordered_set 中的元素是唯一的，不允许重复。
• 这意味着如果尝试插入一个已经存在的元素，插入操作会被忽略。

（3）无序性

• unordered_set 中的元素是无序的，不保证元素的存储顺序。
• 如果需要有序集合，可以使用 set（基于红黑树实现）。

（4）动态扩展

• unordered_set 的容量可以动态扩展，不需要手动管理内存。