发现 \(nk\) 可行，猜测是 \(O(nk)\) 的 DP。
容易想到设计 \(dp[i][j]\) 表示前 \(i\) 个物品，允许恶魔使用 \(j\) 次魔法的最大价值。
但是这样转移是有后效性的，因为恶魔可能在只考虑前 \(i\) 个物品的时候 与 只考虑前 \(j\) 个物品的时候 对于某个物品是否要使用魔法的决策不同。
这种情况下一种办法是考虑贪心，把 DP 的顺序确定下来。
比如这题，我们断言：最优的买物品的顺序一定是按 \(v_i\) 升序购买。
证明：对两个物品 \((v_1,c_1),(v_2,c_2)\)，假设 \(v_1<v_2\)。\(v_1,v_2\) 的顺序的结果是 \(\min(v_1-c_1,v_2-c_1-c_2)\)，\(v_2,v_1\) 的顺序结果是 \(\min(v_2-c_2,v_1-c_1-c_2)\)。
因为 \(v_1<v_2\)，所以 \(\min(v_2-c_2,v_1-c_1-c_2)=v_1-c_1-c_2<\min(v_1-c_1,v_2-c_1-c_2)\)。所以前者总是比后者更优。证毕。
把物品按 \(v\) 升序排序。按 \(n\rightarrow 1\) 的顺序递推即可。（因为当恶魔决定要不要对 \(i\) 施法，与其相关的是 \(i+1\sim n\) 的情况）
标签：nk,P4765,Imp,升序,恶魔,物品,DP From： https://www.cnblogs.com/FLY-lai/p/18552696