P1070 题解
__vector__
·
·
题解
参照：洛谷本题第二篇题解。
首先，注意到从 i 走到 i+1 的边的边权可以算到 i+1 的点权上，这样就将边权转化为了点权。
设 f_i 代表时间为 i 的最大收益。
$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}$。
接下来每个对角线维护一个单调队列就搞定了。