题解
动态规划
定义 f[i] 表示到达任务 i 的最小总执行时间。同时维护一个 t 数组来记录最优路径。
状态转移：
- 对于每个任务，我们考虑从之前的 maxStep 范围内的任务跳转到当前任务。
- 如果找到一个更好的路径（总执行时间更小），就更新
f[i] 和 t[i]。
- 其转移可以用单调队列优化
代码
from collections import deque
小友所在的部门正在进行一系列复杂的开发项目。为了优化开发流程，部门要求工程师在不同的任务之间切换。每个任务有不同的执行时间，有些任务因为各种原因无法进行（标记为-1）。工程师可以在规定的跳跃范围内从一个任务跳到另一个任务，但每次执行任务必须要消耗相应的时间。
你的目标是找到一个从任务列表开头到结束的执行顺序，使得总执行时间最小。如果存在多个总执行时间相同的顺序，返回按索引值更小优先的顺序。如果无法到达最后一个任务，返回一个空数组。
规则
- 输入一个整数数组 tasks 表示任务执行时间，长度为n。
- 输入一个整数 maxStep 表示单次切换任务的最大切换长度。
- 你从任务列表的第一个任务开始 (tasks不是-1)。
- 从任务i切换到任务j，消耗的时间为 tasks[j]。
- 如果你当前位于任务i，你只能跳到任务 i + k（满足 1 ≤ k ≤ n），其中 k 在范围 [1, maxStep] 内。
- 返回一个整数数组，包含你访问的任务索引顺序，使得总执行时间最小。如果多个相同总执行时间的顺序，返回索引值最小的顺序。
排序说明
如果存在多个总执行时间相同的顺序：
- 假设方案 p1 = [Pa1, Pa2, ..., Pax] 和方案 p2 = [Pb1, Pb2, ..., Pbx]。
- 如果在两个方案中第一个不同的索引j处，Pa[j] 小于 Pb[j]，则选择方案 p1。
- 如果所有索引都相同，但任务切换次数不同，则选择任务切换次数较少的方案。
提示： 注意排序规则，如1-2-3-4-5和1-4-5 假设两个方案所消耗的时间相同。
输入描述
- 整数 N，代表任务 tasks 的长度
- 长度为 N 的数组 tasks 的各个元素
- 整数 M，代表每次切换任务的最大跳跃长度
输出描述
输出数组，代表总执行时间最短，并且索引值最小的执行方案
补充说明
- 1 ≤ tasks.length ≤ 1000
- -1 ≤ tasks[i] ≤ 100
- tasks ≠ -1
- 1 ≤ maxStep ≤ 100
示例 1
输入
5
1 2 4 -1 2
2
输出
1 3 5
示例 2
输入
5
1 2 4 -1 2
1
输出
[]
说明
无法到达最后一个任务，输出字符串"[]"
