P12678 Brooklyn Round 1 & NNOI Round 1 B - Gift 笔记

容易想到为了往最优贡献靠，一定按 $b_i$ 升序排序选。

考虑暴力，设 $f_{i,j}$ 表示考虑前 $i$ 个数，$\sum b_i=j$ 的最优答案，则

$$f_{i,j+b_i}\leftarrow max\{\begin{array}{lll}{f}_{i,j}+a_i& b_i<j& (1)\\ f_{i,j}+a_i\times b_i& b_i\ge j& (2)\end{array}$$

时空复杂度 $O(nmax{b}_i)$。

考虑优化，题目给出了 $\sum b_i\le 5\times {10}^6$，而转移 $(2)$ 恰好又是 $O(\sum b_i)$ 的，所以重点在于解决转移 $(1)$。

由于 $(1)$ 和 $(2)$ 对立，因此考虑每个人的基础贡献都是 $(1)$，然后对 DP 的贡献进行 $(1{)}^{\prime }=0,(2{)}^{\prime }=(2)-(1)$ 的操作，即将 DP 中的贡献计算全部减去 $a_i$，这样就只需进行 $(2{)}^{\prime }$ 转移即可。时空复杂度 $O(\sum b_i)$。