【每日一题】5月27日题目精讲 完全背包

题号 NC21228
名称 货币系统
来源 2018NOIP复赛-提高组Day1
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

首先我们要想到，最后的最小的货币系统应该是原货币系统的一个子集，原因也很简单——如果a能够用其他一个或若干个面值表示那么它显然不必要，而如果你去引入一个原来不存在的数那么要么是多于的（能被原来货币系统里面的一个或多个数表达）要么就会引入新的东西。
所以现在我们要做到就是在刚刚的集合里面求所有必要的无法被替代的货币数量。
显然，最小的数肯定要留下，因为其他数字肯定表示不了它。
然后第二大的数，如果是最小的数的倍数就不需要，不是就得留下。
再考虑第三大的，假设前两个数都留下了，显然，如果它是前两个数能组成的数那肯定就可以删掉了。
依此类推，每个数如果能被小于它的数组成，就删掉。
现在问题就变成了：给你若干个数，他们每个都可以使用无穷多次，问能组成的数有哪些——这不就是个典型的完全背包么？只是把最大价值变成可能性问题了而已，于是就很好解决了。
f[i]表示当前这个数x之前的数能不能组成i，如果f[x]等于1，那么说明x可以删了，删掉即可；如果f[x]是0，那么x不能删，就按完全背包的方式更新f数组。

看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目6月3日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴