Knapsack with Diminishing Values

题目描述

有 $N$ 种物品。第 $i$ 种物品的重量是 $w_i$，价值是 $v_i$。每种物品都有 $10^{10}$ 个可用。 Takahashi 将选择一些物品放入容量为 $W$ 的背包。他想在避免选择过多同一类型物品的前提下使所选物品的总价值最大化。因此，他将选择第 $i$ 种物品 $k_i$ 个时的幸福度定义为 $k_i v_i - k_i^2$。他想在总重量不超过 $W$ 的条件下选择物品以使所有类型的幸福度总和最大化。计算他能获得的最大总幸福度。

输入格式

输入从标准输入按以下格式给出： $N$ $W$ $w_1$ $v_1$ $w_2$ $v_2$ $\vdots$ $w_N$ $v_N$

输出格式

输出答案。

2 10
3 4
3 2

5

3 6
1 4
2 3
2 7

14

1 10
1 7

12

提示

$1 \leq N \leq 3000$ $1 \leq W \leq 3000$ $1 \leq w_i \leq W$ $1 \leq v_i \leq 10^9$ 所有输入值均为整数。通过选择第 $1$ 种物品 $2$ 个和第 $2$ 种物品 $1$ 个，总幸福度可以是 $5$，这是最优的。 这里，第 $1$ 种的幸福度是 $2 \times 4 - 2^2 = 4$，第 $2$ 种的幸福度是 $1 \times 2 - 1^2 = 1$。 总重量是 $9$，在容量 $10$ 以内。

标签: AtCoder|abc373F

来源

AtCoder|abc373F