P4765 [CERC2014] The Imp 解题笔记

原题链接

题面

商店里有 \(n\) 个魔术实体，每个实体都锁在一个特殊的魔术宝箱中。第 \(i\) 个宝箱（和其中的实体）的售价为 \(c_i\)个金币，而其中实体的价值相当于 \(v_i\) 个金币。

然而像你这样的凡人，只能安全地携带一件魔法实体。因此，你想要得到最宝贵的一个。

小恶魔可以将某一个魔术宝箱内的实体转化为毫无价值的灰尘。当然，他会在你购买一个魔术宝箱后立即对其使用该魔法，这样你就为这个宝箱付了钱而没能得到里面的实体。

小恶魔拥的魔力最多可以用来使用 \(k\) 次魔法。当然，他可以不用完这 \(k\) 次魔法，而你也可以随时空手走开（尽管这是一个奇耻大辱）。但是，如果你成功地买到了到一个实体（而没有被变成灰尘），则你必须保留该实体并离开商店。

你的目标是最大化你的收益（所购实体的价值减去支付的所有费用（包括购买当前实体和之前的灰尘）），而小恶魔则希望将其最小化。如果你和小恶魔都使用最佳策略，那么你的收益将会相当于多少金币？

solution

由于凡人一次只能带一个实体，所以凡人的策略其实是确定的，将数组 \(v_i\) 排序然后一个一个选择买还是不买。

我不会证明。

而小恶魔的策略有点难办，使用 dp 解决

将 \(v_i\) 从大到小排序，设 \(dp_{i, j}\) 为选择前 \(i\) 个，小恶魔用了 \(j\) 次魔法时的最大收益。

那么使用 \(0\) 次魔法时的状态转移方程为 \(dp_{i,j} = \max(dp_{i - 1, 0}, \min(v_i, c_i))\)

由此推出使用 \(j\) 次魔法时的状态转移方程为 \(dp_{i, j} = \max(dp_{i - 1, j}, \min(v_i - c_i, dp_{i - 1, j - 1} - c_i))\)

code