P14207 [ROI 2016 Day1] 捕捞，还是不捕捞？

Nygglatho · 2025-11-13 01:16:04 · 题解

显然你一定是移动到捕捞点或者基地之后返回，然后逆流而上时仅捕捞，顺流而下时仅出售肯定是最优的。

不妨考虑枚举移动到哪个点之后返回。

先考虑查询，查询显然最优策略就是每次尽量选择范围内 c_i 最大的出售，直到对于一个基地出售数量达到 b_i 或者总出售数量达到捕捞的数量 k。

然后这个考虑把 c_i 离散化之后放到线段树里，线段树每个节点维护原本的 c_i，数量 cnt_i 和总价值 val_i，每次查询在线段树上二分。

每次相当于是新加进来一个点，分两种情况：

• 这个点是捕捞点，则 k\gets k+a_i。
• 这个点是基地，则线段树上将离散化后的 c_i 对应的节点的 cnt\gets cnt+b_i,val\gets val+b_i\cdot c_i 即可。

submission，常数比较大。