题解：AT_abc373_f [ABC373F] Knapsack with Diminishing Values

· · 题解

前言

有时候不要用 edge 的 GPT 侧边栏翻译，会把 10^{10} 翻译成 10，害得我罚多了一发。

思路

提供一个很清奇的不用优先队列的解法。

首先，对于此题目的数据范围而言 10^{10} 个物品就是 +\infty，这是因为 W \le 3000,v \ge 1，\max\left\{\frac{w}{v}\right\}=3000 < 10^{10}。

那么为什么不能跑完全背包呢？因为对于同种物品，a 个该种物品的幸福值 av_{i}-a^{2} 和 b 个该种物品的幸福值 bv_{i}-b^{2} 不能叠加成 a+b 个该种物品的幸福值 (a+b)v_{i}-(a+b)^{2}！

遇事不决，先打暴力！

枚举要取多少个物品，枚举每个物品要取多少个，直接跑 0/1 背包。

这是暴力 code。

然后超时了，分析一下，发现是因为当 w_{i} 都很小时，暴力的时间复杂度退化成 O(NW^{2})。让 w_{i} 全部都变得很大肯定是不行的，我们退而求其次，如果 w_{i} 全部不相同，因为当 W 为整数，O(\sum_{i=1}^{W} \frac{W}{i})=O(\ln W)，所以时间复杂度就是 O(NW \ln W)，足以通过本题。

那么只需要预处理出 h_{i,j}——选 j 个重量为 i 的物品可以获得的最大幸福值，而 h_{i,j} 可以通过一个很简单的贪心求得——“选 j 个的最优方案”实际上一定是在“选 j-1 个的最优方案”的基础上将某个物品的数量增加 1。我在赛时只是感知了一下它的正确性就打了，实际上根据开口向下的二次函数的导数递减的性质就能证明。

代码

赛时 code。