LINK 有点像背包,但是又不完全是 原因在于使用的物品有限制,使得物品的使用次序是未知的 这样显然无法扫一遍做背包 如果按照排序也是不对的,限制大的不一定先使用 若使用变为,这样中间错过了许多小型优惠劵,可能先使用中间的才更优 于是想到按照排序,直接做背包即可. 这样选择物品的顺序满足 如果只选择优惠券中的一个,那么顺序是无所谓的,背包会考虑到 如果需要同时选择物品,那么按照的顺序一定是可行的 反证法 设按照的顺序选可行得到 按照顺序选优惠券不可行得到 我们得到,也就是 而因为,移项得到 显然矛盾,证毕,不存在这种情况. 也就是说,按照这种方式排序不会错,直接做背包即可 #include &...