P12378 题解

Helenty · 2025-04-28 12:32:27 · 题解

我们要计算的是，任意次兑换后，某种硬币的数目达到最大。那么容易想到，只有把所有能兑换过去的硬币全部兑换过去，得到的目标硬币数才可能最大。

假设我们的目标硬币是面值为 5（奇数），初始硬币数为 5，并且面值分别为 1+4、2+3 的硬币可以兑换过来。假设目标硬币面值为 4（即偶数），初始硬币数为 4，面值分别为 1+3、2+2 的硬币可以兑换过来。综上，我们可以枚举所有可能的目标硬币情况，对每一个面值的硬币分奇偶讨论他的最大数目，然后求出所有硬币最大值即可。

易得答案为：682425，输出即可。