题解

思路

令 $dp[t]$ 表示恰好连续覆盖完 $M$ 到 $t$ 的最小费用，并令 $dp[M-1]=0$。选择区间 $[l,r]$ 作为最后加入的班次时，先前覆盖终点 $k$ 必须满足 $l-1\le k\le r-1$：左端条件保证没有空缺，右端条件保证新区间确实把覆盖推进到 $r$。

因此转移为

$$dp[r]=\min\left(dp[r],\min_{k=l-1}^{r-1}dp[k]+S\right).$$

做法

把班次按右端点排序，用维护区间最小值的线段树保存已经得到的 $dp$。每个班次做一次区间查询和一次单点取最小更新。答案为 $dp[E]$。

若所有工资为零，只需用经典区间覆盖贪心判断可行性。若 $N\le1000$，可枚举上一个作为结尾的班次进行二次 DP。

复杂度

完整算法时间复杂度为 $O(N\log(E-M+2))$，空间复杂度为 $O(E-M+2)$。

正确性证明

任意完整覆盖方案按所选班次右端点排列。对最后一个右端点为 $r$ 的班次 $[l,r]$，此前方案必须覆盖至某个 $k\in[l-1,r-1]$，否则会留空或不能推进；转移枚举了所有这些合法前驱。反之，任意合法前驱方案加上该班次都会连续覆盖至 $r$。归纳可知每个 $dp[r]$ 都是对应覆盖的最小费用，故 $dp[E]$ 为最优答案。