原题传送门

题目分析

一个特别长的题目，简化一下：

  1. 一个货币系统 ，其中包含 种不同面额的货币，每种货币数量无限。这个系统可能是不完善的，即可能存在某些金额无法被表示。
  2. 要找到一个与原始系统等价的货币系统 ，使得 尽可能小。两个系统等价意味着它们能表示的非负整数集合完全相同。

同时，我们关注以下几个点：

  1. 如果某个面额可以被系统中的其他面额线性组合表示（使用非负整数系数），那么这个面额就是冗余的。
  2. 最小系统就是原始系统中所有不能被其他面额组合表示的面额的集合。
  3. 这实际上是在寻找原始面额集合的"基" - 即最小线性无关组（在非负整数系数下）。

解题思路

很明显，这道题要使用完全背包来解决（这是显然的）。

同时，这道题在做的时候同时给人一种：

这题绝对不是完全背包！

（如上）的错觉。

所以，我们把这道题的主要思路定为：类似于完全背包：

  1. 排序：首先将原始面额按从小到大排序
  2. 初始化：与音量调节一样，创建一个 bool类型的 数组， dp[i] 表示金额 i 能否被表示，初始时只有 dp[0]=true。
  3. 开始DP：对于每个面额 a[i] ：
    • 如果 a[i] 已经被之前的组合表示，则它是冗余的，跳过。
    • 如果 a[i] 不能被之前的组合表示，则必须保留，并用它更新 数组。
  4. 结果：统计必须保留的面额数量

算法正确性证明

  • 如果面额 能被比它小的面额组合表示，那么它确实冗余
  • 如果面额 不能被比它小的面额组合表示，那么它必须保留
  • 通过从小到大处理，确保每个面额只依赖于比它小的面额

复杂度分析

  1. 时间复杂度：，其中 是最大面额
  2. 空间复杂度：

代码实现

AC Code

#include <bits/stdc++.h>
using namespace std;
int t;  // 测试数据组数
int n;  // 货币种数
int a[100];  // 存储面额的数组
bool dp[25001] = {false};  // DP数组，初始化为false
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        // 步骤1：对面额排序
        sort(a, a + n);
        int m = a[n - 1];  // 最大面额
        dp[0] = true;  // 金额0总是可以被表示
        int ans = 0;  // 结果：最小系统的大小
        // 步骤2：遍历每个面额
        for (int i = 0; i < n; i++) {
            // 如果当前面额不能被之前的组合表示，则必须保留
            if (!dp[a[i]]) {
                ans++;
                // 步骤3：用当前面额更新DP数组
                for (int j = a[i]; j <= m; j++) {
                    if (dp[j - a[i]]) {
                        dp[j] = true;
                    }
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

代码详解

变量说明

  • t：测试数据组数
  • n：每组数据的货币种数
  • a：存储面额的静态数组
  • dp：动态规划数组，dp[i]表示金额i能否被表示
  • m：最大面额，用于确定DP数组的范围
  • ans：最终结果，即最小货币系统的大小

算法步骤

  1. 输入处理：读取测试组数和每组数据
  2. 排序：将面额从小到大排序，便于处理
  3. DP初始化：金额0总是可以被表示（使用0张任何面额）
  4. 核心处理：
    • 检查当前面额是否已被表示
    • 如果未被表示，则保留并更新DP数组
  5. 输出结果：输出每组数据的最小系统大小

完结撒花！！