[ABC373F] Knapsack with Diminishing Values 讲解

zrl123456 · 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)。

代码