自动搬运

查看原文

来自洛谷，原作者为

	是青白呀 咕咕咕？咕咕咕！

搬运于2025-08-24 23:01:03，当前版本为作者最后更新于2024-06-30 14:54:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Preparation

根据题意，我们首先给出如下性质。

1. 开行恰好 $k$ 班公交，实际上等价于开行至多 $k$ 班公交，因为你完全可以在 $\infty$ 的时间发若干辆车补齐 $k$ 班，这些车显然不会有人坐。

2. 由于公交车在任意区间的用时都不短于火车用时，所以在规划的方案中，每班车实际服务的换乘站都是一段连续的区间。

3. 假设极长区间 $[l,r]$ 是由同一班车服务的，则为了让总等待时间最短，我们一定让这班车于 $t_l$ 时刻从车站 $l$ 发车。进一步地，由于此后每个车站的等待时间都已经确定，现在的目标就是要最小化该班次的 $v_u$。不难想到我们可以从 $l$ 的前缀车站中 $v$ 最小的一个位置发车。

4. 在性质 $3$ 的基础上进一步简化问题。假设我们对于每个自行确定的区间都安排了一班车去服务它，并且按照上述方式安排发车地点，我们发现，任意一个车站的乘客都可以被认为是乘坐的预期服务该车站的那班车。

   考虑证明这个事情。若这个结论在换乘站 $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)$，则不难进行如下的推导：

$$\begin{aligned} val_{x,y}&=sum_y-sum_{x-1}-(y-x+1)(ns_x-t_x)\\ dp_{i,j}&=\min(dp_{p,j-1}+sum_i-sum_{p}+(i-p)(ns_{p+1}-t_{p+1}))\\ dp_{i,j}-sum_i&=i(ns_{p+1}-t_{p+1})+dp_{p,j-1}-sum_{p}-p(ns_{p+1}-t_{p+1}) \end{aligned} $$

最后这个式子是可以斜率优化转移的。每个转移点 $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}$ 之后，仍然分析其转移是否具有类似的性质。

观察原始转移式子 $dp_{i,j}=\min (dp_{p,j-1}+val_{p+1,i})$。假设 $i-1$ 的转移点为 $q$，则对于任意转移点 $p<q$，有 $dp_{q,j-1}+val_{q+1,i-1}\leq dp_{p,j-1}+val_{p+1,i-1}$。则 $i$ 从 $p<q$ 的位置转移的式子为 $dp_{p,j-1}+val_{p+1,i}$，从 $q$ 转移的式子为 $dp_{q,j-1}+val_{q+1,i}$。我们有 $val_{p+1,i}-val_{p+1,i-1}=v_{p+1}\times w_i$，$val_{q+1,i}-val_{q+1,i-1}=v_{q+1}\times w_i$。由于公交车速度不快于火车速度，故从 $p+1$ 始发的 $w_i$ 一定不小于 $q+1$ 始发的 $w_i$；同时又有 $v_{p+1}\geq v_{q+1}$，故 $val_{p+1,i}-val_{p+1,i-1}\geq val_{q+1,i}-val_{q+1,i-1}$，也即 $dp_{p,j-1}+val_{p+1,i}\geq dp_{q,j-1}+val_{q+1,i}$，从 $q$ 转移一定优于从 $p<q$ 的 $p$ 处转移。上述描述实际上也等价于证明了和 $val$ 相关的四边形不等式成立。

因此，该 dp 的转移具有决策单调性，可以用分治法在 $O(n\log n)$ 的复杂度内完成单层的转移，故总复杂度 $O(n^2\log n)$。

所有对 $k$ 的询问都可以跑完 dp 后一起回答，$p$ 组时刻表中，每一组需要独立跑 dp，故最终复杂度为 $O(pn^2\log n)$，可以通过本题。