[CERC2014] The Imp
恶魔有 \(n\) 个物品，每个物品价值为 \(v_i\)，购买需要 \(c_i\) 元。
恶魔至多可以使用 \(k\) 次魔法，你和恶魔轮流操作：
- 你购买一个物品
- 恶魔要么释放一次魔法销毁这个物品（继续游戏），要么让你拿走这个物品（然后强制结束游戏）
你和恶魔都会采用最优策略，恶魔的目标是最小化你的收益，求你的最大收益。
\(1 \le n,v_i,c_i \le 10^6\)，\(0 \le k \le 9\)
Hard Ver. \(0 \le k \le n\)
先做简单版本的，考虑邻项交换，设我们策略里最后买的两个物品是 \(v_1,c_1\) 和 \(v_2,c_2\)
先 \(1\) 后 \(2\) 是 \(S + \min(v_1 - c_1, v_2-c_1-c_2)\)
先 \(2\) 后 \(1\) 是 \(S + \min(v_2 - c_2, v_1-c_1-c_2)\)
不失一般性地设 \(v_1 \le v_2\)，那么有 \(v_1-c_1-c_2 \le v_2-c_1-c_2 \le v_2 - c_2\)。
同时还有 \(v_1-c_1-c_2 \le v_1 - c_1\)，也就是说右下角那项总是最小的，选择先 \(1\) 后 \(2\) 总是不劣的。
这个时候就能直接 \(\text{dp}\) 了，但是正着比较难推，考虑我们的结构一定是在前缀选了若干被炸，然后最后拿走了一个，所以倒着来更新。\(f_{i,k}\) 表示在后 \(i\) 个物品里选了一些，被恶魔炸了 \(k\) 次：
- \(f_{i,0} = \max(v_i - c_i, \ f_{i+1, 0})\)
- \(f_{i,k} = \max(f_{i+1,k}, \ \min(f_{i+1,k-1}-c_i, \ v_i - c_i)\)
答案是 \(f_{1,k}\)，这样是 \(O(nk)\) 的。
这个题我是 23 年做的，最近发现有人发明了 \(0 \le k \le n\) 的 hard ver，看一下怎么做。。。
我擦，做法是二分答案以后，正着反悔贪心（原来 dp 不容易正着做是因为这个 ???）。
就是说如果可以按顺序选出 \(k + 1\) 个物品，满足每个物品的 \(v_i - c_i - S \ge ans\) 那么这个二分的答案就合法，这里 \(S\) 是当前已选了的物品的 \(\sum c_i\)。
这个条件是充要的，即恶魔没有办法在任何时候提前结束，使得你的答案小于 \(ans\)，非常牛的转化。
如果 \(v_i - c_i - S\) 合法那么就直接贪心拿进来，然后把 \(c_i\) 放到堆里等着反悔。
如果拿不进来，就去堆里找一个最小的 \(c' \lt c_i\) 替换前面选的决策，而因为 \(v_i \ge v'\) 所以这样替换一定是合法的。
这样就 \(O(n \log^2 n)\) 了，非常自然的做法，而且很符合直觉，非常牛。