本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-02 19:05:29

[ABC373F] Knapsack with Diminishing Values

题目考察：背包。
题目简述：
给你一个背包和 $n$ 个物品，第 $i$ 个物品代价为 $w_i$，价值为 $v_i$，数量为 $1145141919810$，出题人为了让这个题变难设你选择第 $i$ 个物品 $k$ 次，那么他会将你获得的价值变为 $kv_i-k^2$。在代价不大于 $w$ 的基础上，求你获得的最大价值。
数据范围：

• $1\le n,w\le 3000$
• $\forall i\in[1,n],1\le w_i\le w,1\le v_i\le 10^9$

暴力的多重背包时间复杂度为 $\Theta(nw^2)$，显然不可行。
我们发现，每多选一个第 $i$ 个物品（设以前选了 $k$ 个）就会增加 $v_i-1-2k$ 价值，我们将一个物品拆成 $v_i-1,v_i-3,\dots$ 这些新物品（当然了，价值为负的不能取）。由于代价相同的我们优先选价值高的，所以我们将代价（$w_k$）相同的放在一起，并降序排序，并取前 $\displaystyle\lfloor\frac{w}{w_k}\rfloor$ 个（因为只有这些有贡献）进行 dp。
这样时间复杂度是调和级数，为 $\Theta(nw\log w)$。

代码