企业官网建设流程全解析

打开每日打卡计划，今天轮到的题号是P5020，名字叫“货币系统”，来自NOIP 2018提高组。说实话，第一次看到这个标题的时候，我很自然地往数论方向想，因为“货币系统”这四个字听起来就很像gcd、同余那一套。但仔细读完题目就会发现，它其实是一道彻头彻尾的动态规划题，而且核心思想非常朴素——如果一个面额能用更小的面额凑出来，那它在这个货币系统里就是多余的。这个判断逻辑，配合完全背包，就能在O(n×maxA)的复杂度内轻松解决。这篇文章我从头到尾拆一下这题怎么做、为什么这么做，顺便把我踩过的坑也一并倒出来，希望能对正在啃NOIP真题的选手有帮助。

1. 先把题目读懂：货币系统到底在问什么

1.1 题意与样例拆解

题目描述并不长，但信息密度很高。大致意思是：现在有一种货币系统，里面有n种面额的货币，面额分别是a1, a2, ..., an。我们要找到另一个货币系统，使得这两个系统能够表示出来的金额集合完全一致，并且新的系统面额种类数要尽量少，最后输出最少的种数。

我举个非常经典的例子。如果原系统是[3, 19, 10, 6]，面额有4种，那么它能表示什么样的金额？比如6可以表示成3+3，19可以表示成10+3+3+3，而这些金额在系统[3, 10]里同样都能表示出来。反过来说，[3, 10]能表示的金额，原系统当然也都能表示。所以这两个系统是等价的，而后者的面额种类数只有2，比原来的4更优。最终答案就是2。

这一步理解非常重要：题目不是要求你找出某种“最小面额组合”的表示方式，而是要求你在面额集合上做减法，尽量删掉冗余项，直到剩下的面额谁也“离得开谁”。

1.2 等价系统背后的“删数”逻辑

一个货币系统如果删掉某个面额，剩下的面额仍然能把这个面额本身表示出来，那么这个面额就是冗余的，删掉它不会影响整个系统能表示的金额集合。反过来思考：如果我们不断重复这个“检查-删除”的过程，最终剩下的就是一个极简系统，任何一棵面额都不能被其他面额组合表示。

为什么这样反复删除得到的一定是最优解？这里其实隐含了一个关键性质：冗余判断是局部的，而且删除顺序不影响最终结果。也就是说，如果我的目标是把所有能被其他面额表示的面额都去掉，那么我不需要操心“先删谁后删谁”的问题，因为一个能被其他面额表示的面额，不管其他冗余面额删不删，它始终能被剩下的非冗余面额表示。这一点保证了“排序后从左到右扫描一遍，边扫边删”的做法是可靠的。

所以问题的核心从“求最小等价系统”变成了“求所有不能被其他面额表示的面额数量”。这两者在数学上完全等价，但后者显然更容易用程序实现。

1.3 为什么只需要关注比自己小的面额

如果面额x能够被其他面额的组合表示出来，那么参与组合的每一个面额一定都小于x。这个道理很直白：因为所有面额都是正整数，要把总和凑成x，每一位加数都不可能超过x本身，而且如果某个加数等于x，那就意味着用了一张x面额的货币，这不算“被其他面额表示”。

既然参与组合的面额都小于x，那么我们在判断x是否冗余的时候，根本不需要看那些比x大的面额。这就给算法带来了一个天然的顺序：把所有面额从小到大排序，处理到x时，只需要考虑已经扫描过的较小面额。换句话说，这是一个典型的“在线判断”问题，每扫到一个新元素，就基于之前积累的信息做决策。

这个观察看似简单，却是整道题的关键。很多第一次做这道题的同学会下意识地枚举两两关系，或者急着去想高维背包，但其实只要抓住“只看更小面额”这一点，整个问题的复杂度立刻就降下来了。

2. 核心思路：排序 + 完全背包

2.1 排序的作用远不止方便遍历

先排序是很多题解的“标配”，但很少有人解释为什么排序如此重要。除了“只看更小面额”这个数学原因之外，排序还有一个工程上的必要性：不排序会导致判断顺序错乱。

我举个例子，如果输入是[19, 3, 10, 6]，我们不排序直接扫描，先处理19。此时dp数组里没有一个标志位，19会被误判为“不能被表示”，于是19被保留。然后处理3，3被保留；处理10，10被保留；处理6，6此时可以被3+3表示，所以被删掉。最终得到的答案是3，但正确答案是2。问题就出在19被过早地保留了，等到后面发现3和10能组合出19时，已经没办法回头删掉19了。

排序之后，我们从3开始处理，再到6、10、19，每一步都基于更小面额已经处理完的状态做判断，就不会出现这种“后悔”的情况。所以排序不是可有可无的预处理，而是贪心判断正确性的前提条件。

另外要提醒一下，这里的排序是对面额数值本身排序，不需要额外记录原来的下标。因为题目最终关心的是面额种类的数量，不是哪些面额被保留了，所以排序后直接处理完全没问题。

2.2 背包模型：把“表示”变成“可达”

判断一个数能不能被若干个给定面额组合出来，这个问题听起来像是搜索，但面额数量最多100，最大面额到25000，搜索显然会爆炸。正确的做法是把“能被表示”看成一种递推状态。

定义dp[j]为一个布尔值，表示“当前已经保留的面额能否组合出金额j”。初始情况是dp[0] = true，因为金额0不需要任何货币就能实现，这是所有背包问题的起点。

当我们新保留一个面额x之后，要对整个背包做一次扩展：如果某个金额j减去x之后对应的dp[j - x]为true，那么j也能被表示，因为只需在凑出j-x的基础上再加一张x面额的货币。写成转移方程就是：

dp[j] = dp[j] || dp[j - x]

这里的循环顺序必须是从小到大。如果从大到小循环，每个面额就最多只能用一次，变成01背包；从小到大循环时，当我们在计算dp[j]时，dp[j - x]可能已经在这一轮更新过了，这意味着x可以被重复使用，正好对应“货币数量无限”这个设定。

我习惯把这种完全背包想成找零钱的过程。你手里有一堆3元硬币，想要凑出一个金额j，可以先凑(j-3)，再补一个3元；而凑(j-3)本身又可以继续拆。只要从3元开始一直向上递推，很快就能把所有能被3整除的金额标成true。这个类比虽然简单，但能很直观地解释为什么内层循环必须从小到大。

2.3 正确性：为什么“不能被表示”就必须保留

这个结论是整个算法最核心的贪心性质。我用自己的话重新证明一遍，方便大家记忆。

假设当前扫描到面额x，dp[x] == false，也就是说，所有的更小面额无论怎么组合都无法凑出x。那么这样的x在一个等价系统中能不被保留吗？不能。因为如果等价系统不包含x，那它只能用比x更小的货币来凑出x；但我们刚刚已经验证过，所有更小的面额都凑不出x，所以不可能。它也不可能用一个更大的面额来凑x，因为更大的面额单独一张就超过x了，更不用说和其他面额组合。

反过来，如果dp[x] == true，说明更小面额能组合出x，那么x一定是冗余的。此时我们不仅可以把x从系统中删掉，还不用担心它的缺失会影响系统表示其他金额的能力——因为所有用到x的地方，都可以直接用组合出x的那组更小面额替代，而替代过程中用到的每一种面额都已经确定被保留了。这个“替换论证”保证了删除的全局安全性。

所以整个算法只有两种情况：能表示就跳过，不能表示就保留并更新背包。每一步都是局部决策，但累加起来就是全局最优解。

3. C++ 实现全过程

3.1 可直接AC的完整代码

下面这份代码是我在实际OJ上验证过的版本，加上了详细的注释，大家可以对照着理解。整个实现非常短，但这正说明这道题考的是思路，而不是代码量。

#include <bits/stdc++.h> using namespace std; const int MAXV = 25005; // 最大面额上限 int a[105]; // 存储所有面额 bool dp[MAXV]; // dp[j] 表示当前保留货币能否凑出金额 j int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } sort(a + 1, a + n + 1); // 先排序，这是贪心正确性的前提 memset(dp, 0, sizeof(dp)); dp[0] = true; // 0 元天然可达 int ans = 0; for (int i = 1; i <= n; i++) { if (dp[a[i]]) { // 当前面额已经能被更小面额表示，说明冗余 continue; } ans++; // 不能被表示，必须保留 for (int j = a[i]; j <= a[n]; j++) { dp[j] = dp[j] || dp[j - a[i]]; } } printf("%d\n", ans); } return 0; }

这个代码的时间复杂度大致是O(n×maxA)，空间复杂度O(maxA)。在最坏情况下n=100，maxA=25000，单个测试点大约是250万次布尔运算，即使有多组测试数据压力也不大。

3.2 逐段拆解：每行代码为什么这么写

很多同学能背下模板，却不清楚每步操作的目的。我挑几个容易忽略的点重点讲一下。

首先是sort。这里的排序不只是为了从小到大处理，更关键的是保证“在处理a[i]时，所有可能参与表示它的更小面额都已经被考虑过了”。如果你写的是sort(a, a+n)那么注意排序区间是左闭右开，我这里写的是1-based下标，所以排序区间是a+1到a+n+1。下标习惯不同容易出错，建议统一用一种写法。

然后是memset。题目有多组测试数据，dp数组必须清空。如果漏掉这一步，上一组数据留下的true会在下一组数据里造成误判，轻则答案偏小，重则直接WA。我见过不少选手在考场上因为忘记memset丢掉整道题的分，这种失误是完全可以通过模板化的“每组数据先初始化”来避免的。

再来看主循环里的判断逻辑：

if (dp[a[i]]) continue;

这行代码执行的时候，dp数组里已经包含了所有“已保留的较小面额”能够凑出的金额。如果a[i]已经被标记为true，那说明它不需要保留。这个判断必须在背包更新之前完成。有一个隐蔽的坑是：如果你先把背包更新了，再判断dp[a[i]]，那么新面额x自己也会因为dp[0]为true而把dp[x]更新为true，导致所有面额都被误判为冗余，最后答案输出0。这一点一定要记牢。

最后是内层循环：

for (int j = a[i]; j <= a[n]; j++) { dp[j] = dp[j] || dp[j - a[i]]; }

j的起点是a[i]，因为j - a[i]不能小于0。j的上界是a[n]，也就是当前系统中最大的面额。这里其实有一个值得思考的问题：为什么只需要更新到最大面额就够了？因为后续所有面额的值都不会超过a[n]，我们判断dp[k]时，k最大就是a[n]。如果去更新那些大于a[n]的金额，不仅浪费计算，还需要把dp数组开得更大。把这个上界收紧，既能减少循环次数，又不需要额外担心数组越界。

还有一个细节是dp[j] = dp[j] || dp[j - a[i]]。这个写法保留了dp[j]原来的值，再并入新推出的可达状态。直接用dp[j] |= dp[j - a[i]]也可以，效果完全一样。但要注意左右两边的语义：右边的dp[j]是旧值，左边的dp[j]是更新后的新值。从小到大循环时，dp[j - a[i]]很可能已经因为这一轮更新变成了true，这正是完全背包“无限使用”的实现方式。

3.3 复杂度分析与优化方向

这道题的数据范围其实给得很温和：n不超过100，面额不超过25000。即使不做任何优化，最坏情况也就250万次操作，在C++里跑起来基本是瞬间的事情。所以大家完全不用为了常数去折腾复杂的位运算优化。

不过如果真要在极限数据下压常数，可以用std::bitset来维护dp数组。把dp定义成bitset<25005>，更新操作在概念上相当于把整个dp右移x位后再取或。但这里有个坑：完全背包的“无限使用”语义，需要反复移位直到集合稳定，而不是像01背包那样一次移位就能搞定。所以bitset优化的实际收益没有想象中那么大，反而代码可读性会下降。作为竞赛代码，我更推荐直接用bool数组加循环，思路清晰，也足够AC。

空间方面，25005个bool只需要25KB左右，完全不用吝啬。我见过有人为了省空间把dp改成unsigned char甚至bitset，但在这个题里完全没有必要，保持简单才是最重要的。

4. 刷题踩坑与排查实录

4.1 常见错误TOP5

这道题我前前后后写过好几个版本，也帮别人调试过不少次，总结出五个最常见的出错点，列成表格方便大家自查。

我特别想展开说说第二个坑。很多同学背熟了“01背包倒序，完全背包正序”这个口诀，但没有真正理解为什么。实际上，如果这道题用倒序循环，那么每种面额只能使用一次。举个例子，面额为3，倒序计算时，dp[6]会被dp[3]更新吗？不会，因为3还没被更新到，dp[3]始终是false。于是6就无法被3+3表示出来，但货币系统里3元是可以重复使用的。这就导致后面的判断出错，最终答案偏大。

如果大家在做题时发现答案跟自己手算的不一样，可以优先检查一下循环方向是不是写反了，这是正确解法里最常见的变体错误。

4.2 调试技巧：把dp数组打出来看

我调试这道题时最喜欢用的方法，是在每次更新完背包后打印dp数组的一部分，肉眼观察哪些位置被标记成了true。这个方法特别适合验证自己的算法理解。

用[3, 6, 10, 19]这组数举例。排序后顺序不变。处理第一个面额3时，dp[3]是false，所以ans变为1，然后开始更新背包。从小到大循环一遍后，dp[3]、dp[6]、dp[9]、dp[12]、dp[15]、dp[18]这些3的倍数全部变成true。

处理第二个面额6时，看一眼dp[6]，已经是true，所以直接continue。6不会成为新的保留面额，不需要二次更新背包。

处理第三个面额10时，当前dp[10]还是false，因为3的倍数没有覆盖到10。于是10被保留，ans变为2。然后再做一次完全背包更新，把10、13、16、19、等等全部标成true。此时19已经被标成true了。

处理第四个面额19时，dp[19]已经是true，直接跳过。最终ans等于2，和前面手动模拟的结果一致。

把dp数组打出来看，还能直观感受到背包的“覆盖”过程。如果发现某个面额在你预期中应该被跳过，但dp值却是false，那就说明之前某一步的更新范围或者循环方向出了问题。

4.3 边界数据自测

比赛时没有调试器，只能靠一些边界测试用例来验证代码的健壮性。我建议每组同学在交题前至少手测这几类数据。

第一类是n=1的情况。只有一种面额，比如[5]，答案必须是1。这个用例主要验证基本流程是否走通：5不能被0以外的任何金额表示，所以必须保留。

第二类是重复面额。[2, 2, 2]排序后处理第一个2，保留并更新背包，之后两个2都会因为dp[2]为true而跳过，最终答案是1。这验证了代码对重复面额天然免疫，不需要额外去重。

第三类是互质面额混合。[2, 3, 5]处理2保留，处理3时dp[3]是false所以3也保留，处理5时dp[5]已经被2+3标成true，所以5被跳过，答案2。这个用例能验证完全背包是否能正确合并不同面额的组合效果。

最后一种是大规模极限数据。可以构造n=100、所有面额从1到25000稀疏分布的情况，跑一下确认没有超时、没有数组越界。通常这题的数据规模不会卡常数，但跑一遍自己心里更有底。

5. 从这道题带走的思考

5.1 一个可以推广的模型

货币系统这道题表面上是背包DP，背后其实是一种更通用的“集合简化”模型：给定一些元素，如果一个元素能够由其他元素通过某种运算组合得到，那它就是冗余的，最终留下来的是这个集合下的“基底”。

这种思想在线性基里也有体现，只不过线性基的组合运算是异或，而且每个元素最多使用一次。这里的货币组合是加法，每个面额可以无限次使用。如果把这两个维度拆开看，就能发现它们只是在“组合方式”上不同，而“删冗余求基底”这个核心框架是完全一致的。

以后再遇到描述为“找到最小的集合，使得所有状态都能被覆盖”这样的题目，可以先想想是否存在“某个元素能被其他元素表示”的判断方式。如果能，那么排序加某种递推大概率是最直接的解法。

5.2 刷题打卡的一点体会

坚持刷题打卡这件事，说到底考验的不是每天做多少道题，而是能不能在每道题里都留下一点自己的思考。比如这道货币系统，如果我当初只是看了一下题解，把代码输进去AC，那我大概只会记住“排序+完全背包”这七个字，下次换个包装的同类题照样不会做。但当我真的去推了一遍“为什么dp[x]为false就必须保留”，再模拟了几组样例之后，这个模型就彻底变成自己的东西了。

所以我建议大家在打卡刷题的时候，不要着急追求“今天一定要斩获几道新题”，而是挑几道经典题，像我这样把思路、证明、坑位、边界都写下来。一道题吃透，往往比草草刷十道题更有价值。

最后再分享一个小技巧：拿到这类“等价系统”题目，先别急着套算法，先问自己一个问题——什么情况下一个元素是冗余的？找到这个判断标准之后，再去想用什么数据结构来高效验证它。这个思考顺序，几乎可以应对所有类似的问题。