在网友的国度**有 种不同面额的货币，第 种货币的面额为 ，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 、面额数组为 的货币系统记作 。 在一个完善的货币系统中，每一个非负整数的金额 都应该可以被表示出，即对每一个非负整数 ，都存在 个非负整数 满足 的和为 。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 不能被该货币系统表示出。例如在货币系统 , 中，金额 就无法被表示出来。 两个货币系统 和 是等价的，当且仅当对于任意非负整数 ，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。 现在网友们打算简化一下货币系统。他们希望找到一个货币系统 ，满足 与原来的货币系统 等价，且 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 。 输入 输入文件的第一行包含一个整数 ，表示数据的组数。 接下来按照如下格式分别给出 组数据。 每组数据的第一行包含一个正整数 。接下来一行包含 个由空格隔开的正整数 。 输出 输出文件共有 行，对

以下是解决该问题的Python代码： ```python # 读取数据组数 T = int(input()) for _ in range(T): # 读取货币种数 n = int(input()) # 读取面额数组 coins = list(map(int, input().split())) # 对面额数组进行排序 coins.sort() max_amount = coins[-1] # 初始化动态规划数组 dp = [False] * (max_amount + 1) dp[0] = True # 用于记录最终保留的货币数量 ans = 0 for coin in coins: # 如果当前面额不能由之前的面额组合得到，则保留该面额 if not dp[coin]: ans += 1 # 更新动态规划数组 for j in range(coin, max_amount + 1): dp[j] = dp[j] or dp[j - coin] print(ans) ``` 代码解释： 1. 读取输入：首先读取数据的组数`T`，然后对于每组数据，读取货币种数`n`和面额数组`coins`。 2. 排序面额数组：对面额数组进行排序，方便后续处理。 3. 初始化动态规划数组：创建一个长度为`max_amount + 1`的布尔型数组`dp`，其中`dp[i]`表示金额`i`是否可以被表示出来。初始时，`dp[0]`为`True`，因为金额0可以不使用任何货币表示。 4. 遍历面额数组：对于每个面额`coin`，如果`dp[coin]`为`False`，说明该面额不能由之前的面额组合得到，因此保留该面额，并更新动态规划数组。 5. 更新动态规划数组：对于每个可以使用当前面额`coin`表示的金额`j`，更新`dp[j]`为`dp[j] or dp[j - coin]`。 6. 输出结果：最后输出保留的货币数量`ans`。 复杂度分析： - 时间复杂度：$O(T * n * max_amount)$，其中$T$是数据组数，$n$是货币种数，$max_amount$是最大面额。 - 空间复杂度：$O(max_amount)$，主要用于存储动态规划数组。 [2025-12-13 10:29:25 | AI问答 | 529点数解答]