abc415g 题解

· · 题解

观察

令 f_i 表示初始有 i 杯饮料的答案，然后可以列一个 DP，f_i = \max(i,f_{i-a_j+b_j}+a_j)。然后就 \Theta(nm) 了。

但是显然在 a_j 相同的情况下，我们会选择 b_j 尽量大的物品。所以就 \Theta(nV) 了。

另一个观察就是当 i>V 的时候，我肯定会从某个 f_{i-a_j+b_j} 转移过来，所以这个可以规约成背包问题。

Solution 1

直接 (\max,+) 矩阵乘法优化它，时间复杂度 \Theta(M+V^3 \log n)，可以冲过去。

link

Solution 2

找到那个性价比最高的物品，令它的体积为 Q，则我们可以证明，除了这个物品之外的其它的物品，最多选 Q 个。

为什么呢？

如果其它的物品选的数量 >Q 个，那么这些物品必定存在一个子集，满足这个子集的体积之和是 Q 的倍数⭐，然后把这个子集替换成性价比最高的物品，肯定不劣。

⭐：把这些物品排成一排，根据鸽巢原理必定会存在一个区间的体积之和为 Q 的倍数，也就是存在一个子集。

所以我们不妨把 f_{1} \sim f_{V^2} 暴力预处理出来，然后不断拿性价比最高的物品直到 n \leq V^2，然后加上 f_n 就好啦。

时间复杂度 \Theta(M+V^3)，轻松通过。

link