BZOJ 5018 [Snoi2017] 英雄联盟

发布于 2017-09-02  238 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=5018

https://loj.ac/problem/2256

题意:见原题面。


贪心的策略是尽可能买便宜而且多的皮肤,然后背包 dp,\(f_{i,j}\) 表示考虑前 i 种皮肤花了 j 元的最大展示策略。

考虑证明的话... 我随便 YY 了一下:

如果在某一时刻,最优解不是买一个目前最便宜的皮肤,而是买了另外一个。

那么带来的收益就是除去买的那个皮肤以外的皮肤买的数量的连乘。在这里,只有我们考虑的那两个皮肤才是有用的,别的都可以约下去。

那么显然便宜的那个皮肤可以买的更多,带来更大的收益,或者说至少不会更劣。

就酱... 说错了别骂我

 


一个非常弱的准退役OIER