The Fewest Coins G：题解

思路

设 John 付款总额为 $T+x$，则店主找零 $x$。分别定义：

• pay[y]：John 用有限硬币凑出金额 $y$ 的最少枚数；
• change[x]：店主用无限硬币凑出金额 $x$ 的最少枚数。

答案为所有可行的 pay[T+x]+change[x] 的最小值。

令最大面值为 $V$。只需枚举 $0\le x\le2V^2$。在最少找零方案中，非 $V$ 面值硬币少于 $V$ 枚；否则考察前缀和模 $V$，可找出总值为 $V$ 倍数的非空子集，并用更少的面值 $V$ 硬币替换。当 $x\ge2V^2$ 时，找零至少包含 $V$ 枚最大面值硬币。付款总值也至少为 $2V^2$，任取 $V$ 枚付款硬币，同样能找出总值为 $qV$、$q\le V$ 的非空子集；同时取消这些付款硬币和找零中的 $q$ 枚最大面值硬币，净付款不变而转手硬币数减少，矛盾。因此至少存在一个最优方案满足该上界。

做法

change 使用完全背包。pay 是多重背包：处理面值 $v$、数量 $c$ 时，按模 $v$ 的余数分组。对金额 $r+qv$ 有

next[r+qv] = q + min(old[r+pv]-p)，其中 $q-c\le p\le q$。

括号内是固定宽度滑动窗口最小值，可用单调队列维护。每种硬币对应的每个金额只进出队一次。

复杂度

时间复杂度为 $O(N(T+2V^2))$，空间复杂度为 $O(T+2V^2)$。金额上界不超过 $38800$。

子任务 1 可枚举 John 对每种硬币的使用数量；子任务 2 可在多重背包中直接枚举当前硬币使用 $0\sim C_i$ 枚；满分使用上述单调队列优化。