[Solution] LNOI2022 food

KaguyaH · 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)。