[OOI 2023] 回家的路

chen_zhe · 2025-07-30 14:25:06 · 题解

本题解是官方题解的 AI 中文翻译。

子任务 1. 如果所有 w_i = 1，那么答案就是最短路长度减去 p，可以用 Dijkstra 算法在 O(m \log n) 内找到。

子任务 4. 如果所有 s_i \leq 100，可以设计状态 dp[v][ans] = \text{最大剩余金钱}，转移方式类似 Dijkstra 算法。注意到答案不会超过 S \cdot n，其中 S = \max s_i。因此总复杂度为 O(S \cdot n \cdot (n + m) \cdot \log n)。

子任务 2. 注意表演可以“延后”进行。当我们钱不够过某条边时，可以在已经经过的顶点中提前多次表演，以获取最多的钱。如果图是一个两端分别为 1 和 n 的链（bamboo），只需在前缀中维护 w_i 最大的顶点，每当钱不够时就在该顶点表演。这样复杂度为 O(n)。

完整解法. 借鉴子任务 2 的思路，可以设计状态 dp[v][best] = (\textit{最少表演次数}, \textit{最大剩余金钱})，其中 v 表示当前所在顶点，best 表示已经经过的、w_i 最大的顶点。可以证明，最优策略是先最小化表演次数，再最大化剩余金钱。该动态规划的转移方式与子任务 4 类似，总复杂度为 \mathcal{O}(mn \log n)。