题解

思路

把终点看成位置 $d_{n+1}=\ell$，但它不是可移除标志，也没有新的限速。

设 dp[i][r] 表示保留第 $i$ 个标志、已经移除恰好 $r$ 个标志并到达 $d_i$ 时的最短时间。若下一个保留的标志是 $j>i$，则中间的 $j-i-1$ 个标志全部被移除，这一段一直使用 $a_i$，新增时间为

$$(d_j-d_i)a_i.$$

因此可转移到

$$dp[j][r+j-i-1]\gets\min\bigl(dp[j][r+j-i-1],\ dp[i][r]+(d_j-d_i)a_i\bigr).$$

答案是终点状态中移除数不超过 $k$ 的最小值。

做法

当 $n\le18$ 时，可以枚举除起点外所有标志的删除集合，直接计算每个合法集合的通行时间，复杂度为 $O(n2^{n-1})$。

当 $k\le1$ 时，先计算不删除标志的时间。若删除第 $i$ 个标志，只会合并它左右两段；枚举被删标志并用常数次运算计算新时间即可，复杂度为 $O(n)$。

正确性证明

任意合法删除方案都唯一确定一个递增的保留标志序列：序列以起点开始、以终点结束。相邻两个保留位置 $d_i,d_j$ 之间恰好删除 $j-i-1$ 个标志，并且整段通行时间必为 $(d_j-d_i)a_i$。

DP 的每次转移正好选择保留序列中的下一项，正确累加这一段的删除数与时间。于是每个合法删除方案都对应一条从起点到终点的 DP 路径；反过来，每条删除数不超过 $k$ 的 DP 路径也唯一给出一个合法方案。DP 对所有路径取最小值，因此所得答案就是最短通行时间。

复杂度分析

共有 $O(nk)$ 个状态，每个状态枚举下一个保留标志，时间复杂度为 $O(n^2k)$，空间复杂度为 $O(nk)$。