BZOJ 5018 [Snoi2017] 英雄联盟


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

https://loj.ac/problem/2256

题意:见原题面。


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

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

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

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

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

就酱... 说错了别骂我

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 5018 [Snoi2017] 英雄联盟


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,