DRAFT P14636 [NOIP2025] 清仓甩卖
题解
首先我们转化一下题面,能拿到的最大价值实际上就是对于选出的方案做 0/1 背包,我们要求的就是有多少种取值使得贪心策略达到背包最优解。
考虑如何计数,正着计数显然不可行,考虑什么时候贪心不合法。
由于体积只有 1 和 2,贪心出错的情况一定是选出的物品中,有两个体积为 1 的物品 i,j,并且存在一个未选择的体积为 2 的物品 k,使得 ai+aj<ak。
接下来考虑怎么进行计数,由于 n 范围较小,不妨直接枚举 i,k,统计第一个导致失败的点,这样的话所有糖果可以分成三类:
- 就算 wj=2 也能使得性价比高于 i 的,即必须买的糖果。
- 原价在 [2ai,ai] 之间的糖果,即可能买的糖果。
- 原价 <2ai,即一定不会买的糖果。
需要注意的是,还有一些额外条件,选出的 k 一定要满足 ak>2ai,ak>2aj,只有这样才能让 k 在 i,j 前被考虑,但由于钱不够没有买。
也就是说,在 k 之前需要恰好花光 m−1 元,且 wk=2,wi=wj=1。
如何计数刚好花光 m−1 元呢?由于价格只有 1,2,可以通过在必买和可买中选出若干个物品定价为 2 元,直接组合即可,最终答案为 2n 减去失败方案数。
还有一个小问题,直接枚举复杂度为 O(n3),需要寻找一些优化的办法。
将 a 逆序排序,枚举 k 作为价值为 2 的物品,为了让 k 的性价比高于 i,j 的性价比,要满足 2ak>ai,2ak>aj,即 ak>2ai,ak>2aj,恰好是一定不选的糖果的定义。
钦定 i<j,则 ai≥aj,只需要考虑 i 变大时 j 的变化,根据 ai+aj<ak⟹aj<ak−ai,由于 j 增大时 aj 不增,也就是存在最小的 j 使得 [j,n] 都满足要求,又因为 i<j,不难得到所有 j 的数量为 n−max(i+1,j)+1。
当 i←i+1 时,考虑最小的符合条件的 j 的变化,由于 ak−aj 的减小,aj 上界增大,即 i 增加时 j 最小值递减,那么只需要将最小值和 i+1 取 max 即可。
别忘了乘上前 k 个花掉 m−1 元,j 后面任意选的方案数。
