自动搬运

查看原文

来自洛谷，原作者为

	KaguyaH 嘛。

搬运于2025-08-24 22:38:27，当前版本为作者最后更新于2022-05-26 12:03:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution A

这是考场思路。

显然应先加后乘。显然若 $a_i = 1$ 则必然选择加，首先将这些 $b_i$ 累加到 $x$ 上。如果我们钦定在后面选择加的数对的 $a_i$ 的积为 $A$，则我们应该选择 $b_i$ 和最大的方案。

设 $f_i$ 表示 $\max \sum_{x \in S} b_x \pod{\min_{x \in S} a_x \ge 2 \land \prod_{x \in S} a_x = i}$。每种相同的 $a_x = y$ 只取最大的 $\lfloor \log_y 10^6 \rfloor$ 个，转移类似背包即可。

时间复杂度 $O(n \log n + v \log v \log \log v)$，其中 $v = \max b_i$。

Solution B

显然若 $a_i = 1$ 则必然选择加，首先将这些 $b_i$ 累加到 $x$ 上。

假设我们钦定了选择顺序。对于其余的数对 $(a, b)$，若选择加，则必然有 $x < \frac b {a - 1} \le b$。如果我们在后面选择了多于两个做加法，那么如果我们优先选择 $b$ 最大的那个做加法，其余的选择乘法更优。于是得到结论，$a > 1$ 的数对，至多选择一个做加法。接下来就非常容易做了。

时间复杂度 $O(n)$。