[NOIP2025 T2] 清仓甩卖 题解

P14636 [NOIP2025] 清仓甩卖

不能说是很牛的题目，但是赛时就是没有任何的思路，不知道如何刻画这个不优解的形态，所以还是要认真做一下。

令 \(w_i=1\) 的为一类物品，\(w_i=2\) 的为二类物品。归根到底我们可以发现，选择不优方案当且仅当：有一个性价比较高的一类物品被选择了，导致后面某个性价比没那么高但是价值更高的二类物品无法选择，并且我们还没有办法在后面继续找一个一类物品来弥补损失。具体的，在按照性价比从高到低排序后，我们会选择到 \(\dots x\dots (y)\dots z\)，其中 \(x,z\) 为一类物品，\(y\) 为二类物品，然而这样选不如选择 \(\dots y\dots\)，即 \(a_y>a_x+a_z\)。

既然可以刻画出不合法形态，我们直接对这个形态计数。