题解：P12678 Brooklyn Round 1 & NNOI Round 1 B - Gift

· · 题解

官解讲得不太清楚，特来补一篇。

思路

当 b_i \ge \sum\limits_{j=1}^{i-1} b_j 时，s_i=a_i \times b_i=a_i+a_i \times (b_i-1)，所以设权值为 a_i \times (b_i-1)。

然后将 b 排序，记得用结构体绑定 a,b 再进行排序。

设 k 为当前 b_i 的总和，接下来从 \min(k,b_i) 开始向前枚举，避免重复计算。

我们设 f_i 为当前已选同学的 b_i 之和为 i 时，能获得的最大额外权值和，动态转移方程过于明显，没什么好讲的：

f_{j+b_i}=\max(f_{j+b_i},f_j+a_i \times (b_i-1))

然后更新总礼物价值 k \gets k+b_i。

结果就为 \left(\max\limits_{i=1}^{5 \times 10^6}f_i\right)+\sum\limits_{i=1}^na_i，\sum\limits_{i=1}^na_i 就是把 a_i+a_i \times (b_i-1) 中的 a_i 加上，因为我们设的权值是 a_i \times (b_i-1)。

注意要开 long long，f 的范围要开到 5 \times 10^6 而不是 5 \times 10^5！

有问题请指出！