# 限量补给的旅程 — 题解

Codex（GPT-6）：本题的单调队列动态规划、费用流与次数状态建模、证明、实现和验证；动态规划与费用流为通用方法。

## 油量状态与两个目标

先按位置排序；若起点没有站，补一个库存为零的虚拟站，再加入终点。无限容量可改为 $C=L$ ：任何有剩油的可行方案都能减少某些购买，使总购买恰为 $L$ ，非负单价不会提高费用，次数也不会增加；沿途最多携带 $L$ 即足够。有限容量则令 $C=R$ .

分别维护到达当前站时油量为 $g$ 的最低费用 $dp[g]$ 和最少次数 $cnt[g]$ .初始只有油量零可行。两张表独立优化，不能把费用最优方案的次数当作另一问答案。

设当前价格为 $c$ ，库存截断到 $s=\min(s_i,C)$ .离站油量为 $f$ 时，费用转移为

$$new[f]=cf+\min_{\max(0,f-s)\le g\le f}(dp[g]-cg).$$

随着 $f$ 增加，候选下标是滑动窗口，用单调队列维护括号内最小值，每站 $O(C)$ .不可达状态不参与队列。

次数转移要区分不购买和正数购买：

$$next[f]=\min\left(cnt[f],\ 1+\min_{\max(0,f-s)\le g<f}cnt[g]\right).$$

第二个窗口不含 $f$ ，保证买了正数；空窗口视为不可达。它也能用单调队列线性维护。

完成购买后，若下站距离为 $d$ ，仅保留离站油量至少为 $d$ 的状态，并把下标减去 $d$ .到终点后分别取所有剩余油量状态的最小值；均不可达则输出两个 $-1$ .

## 正确性

给定到站量 $g$ 和离站量 $f$ ，购买量唯一为 $f-g$ .窗口条件恰好表达非负购买、不超过库存和容量，费用增量恰为 $c(f-g)$ ；次数在购买为零时不增加，否则增加一。两式枚举全部且仅有合法决策。行驶平移又恰好枚举能够走完下一段的状态。因此按站点归纳，两张表分别保存所有可行计划的最优目标，终点取最小即为所求。

## 复杂度与贡献

时间 $O(N\log N+(N+1)C)$ ，空间 $O(N+C)$ .费用最多为 $10^9L$ ，使用有符号 64 位整数与足够大的不可达哨兵，计算前排除哨兵。Codex（GPT-6）补齐规格、提出单调队列转移并实现验证，见 [std.cpp](std.cpp)。

[费用流与次数状态方案](solution-alternative.zh.md) 提供不同建模及空间依赖。

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R32.json)