考虑证明这个事情。若这个结论在换乘站 x\in[l,r] 处不成立，一定是有 v 更小的一个班次与预期班次同时到达，或是有 v 不大于预期班次的一个班次更早到达（这样的班次一定是预期服务更靠后的区间的）。在这两种情况下，若换乘站 x 处该结论不成立，则任意 [x,r] 区间内的车站均不成立，且实际情况下的答案都不大于预期情况下的答案。因此我们将实际线路的对应服务区间扩展至 x 处，一定会得到更优答案，因此不合法的情况一定是不优的。
虽然看起来比较长，但其实都是一些容易感受到的内容。
有了这些性质，我们可以直接对 v 做前缀 \min，并认为服务区间 [l,r] 的线路都是从车站 l 直接始发的。
下面设 w_i 表示第 i 个换乘站乘客的等待时间。
Sub 3
简单 dp，设 dp_{i,j} 表示 i 是某个服务区间的右端点，且到 i 为止一共开行了 j 条线路的最小答案。转移枚举上一个服务区间的终点 p，有 dp_{i,j}=\min (dp_{p,j-1}+val_{p+1,i})，其中 val_{x,y}=v_x\sum_{i=x}^y w_i。val 不难在 O(n^2) 的复杂度内预处理出来，转移时直接枚举 p 即可做到 O(n^2k)。由性质 1，我们发现在 k\geq n 时，直接派 n 辆专车接送每个换乘站的乘客即可，直接输出 0，故复杂度 O(n^3)。可以通过 Sub 3。
Sub 5
当 v_i=1 时，val_{x,y}=\sum_{i=x}^y w_i。考虑把 w_i 表示出来，对 s 做前缀和累加，设 ns_i 表示公交车从 1 车站开到 i 车站的总时间，有 w_i=ns_i-ns_x-(t_i-t_x)，再对 ns_i-t_i 做前缀和累加得到 sum_i=\sum_{j=1}^i (ns_j-t_j)，则不难进行如下的推导：
最后这个式子是可以斜率优化转移的。每个转移点 p 在二维平面上的对应点坐标为 (ns_{p+1}-t_{p+1},dp_{p,j-1}-sum_{p-1}-p(ns_{p+1}-t_{p+1}))，不难发现 x 轴坐标是单调不降的，斜率 i 是单调递增的，因此可以直接用单调队列维护下凸壳转移，总复杂度 O(n^2)。当然也可以直接暴力上李超线段树，在 O(n^2\log n) 的复杂度内解决该问题。
Sub 7
当 v_i\neq 1 时，val_{x,y}=v_x\sum_{i=x}^y w_i。这里实际上是给 \min 的部分乘了一个 v_{p+1}，此时式子的乘积项中，含有两个不同的含 i 项，就不能斜率优化了。
注意到 Sub 5 中，最优转移点实际上是单调不降的，我们考虑在外部乘一个系数 v_{p+1} 之后，仍然分析其转移是否具有类似的性质。