本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-08 10:52:08

参照：洛谷本题第二篇题解。

首先，注意到从 $i$ 走到 $i+1$ 的边的边权可以算到 $i+1$ 的点权上，这样就将边权转化为了点权。

设 $f_i$ 代表时间为 $i$ 的最大收益。

$r_{i,j}$ 代表时间 $i$ 到达位置 $j$ 的奖励。

$c_i$ 代表第 $i$ 个工厂的单个机器人花费。

$s_{i,j}$ 代表从 $1$ 时刻开始，一直向前走，走到 $i$ 时刻，到达 $j$ 工厂的总收益。

对于 $f$ 的计算，升序枚举时间 $i$，枚举此时的位置 $j$，然后再枚举上一次机器人走了 $k$ 步到达的当前节点。

$f_i = \max(f_{i-k}+s_{i,j}-s_{i-k,j-k}-c_{j-k})$。

设 $rec_{i,j} = {f_i-s_{i,j}-c_{j}}$。

$f_i = \max(rec_{i-k,j-k})+s_{i,j}$。

接下来每个对角线维护一个单调队列就搞定了。