E - The Imp

有n個物品且分別為價值vi成本ci，然后每次選擇購買后，有人可以使用k次魔法，使得物品消失但是成本仍然花費了，求解最大收益。

首先最后的最優解序列，一定是可以由自己決定的，那么它一定滿足vi遞增，我們可以推導一下，因為必然前面的選擇會被去掉，所以必然不優。

所以我們就把它變成了一個序列問題，然后按照博弈論的策略來dp即可。
但是注意這道題，后面的操作對于前面的操作沒有影響，所以我們可以反著dp。
不過似乎正著也可以。

總結

以上是生活随笔為你收集整理的E - The Imp（博弈/动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。