题解

思路

只需记录每部电梯上一次服务的是哪一名乘客。两次服务之间，电梯若要从上一名乘客的终点移动到下一名乘客的起点，可以选择区间内任意一个该电梯开启的日子完成移动，因此只会选择其中电价最低的一天。

把乘客事件依次编号为 $1,2,\ldots,m$，并设虚拟事件 $0$ 的终点为第 $1$ 层。预处理

$$g_{p,l,r}=\min\{A_d:\ d\in[day_l,day_r],\text{第 }p\text{ 部电梯在第 }d\text{ 天开启}\}.$$

若集合为空，则该转移不可行。

子任务 1

枚举每名乘客选择三部电梯中的哪一部。固定分配后，每部电梯的服务顺序唯一，可以直接累加相邻服务之间的最低移动费和载客移动费。复杂度为 $O(3^Q Q^2)$。

子任务 2

令状态 $(i,j,k)$ 表示三部电梯最后服务的乘客编号。按乘客编号递增转移；选择一部电梯服务当前乘客，并临时扫描两次服务日期间的全部天数求最低可用电价。有效状态数为 $O(Q^2)$，复杂度为 $O(Q^4)$。

子任务 3

先预处理全部 $g_{p,l,r}$，便可在 $O(1)$ 时间计算一次转移。处理完第 $r-1$ 名乘客时，必有 $\max(i,j,k)=r-1$，所以每一层只有 $O(r^2)$ 个有效状态，总复杂度为 $O(Q^3)$，空间复杂度为 $O(Q^2)$。

做法

设当前状态为 $(i,j,k)$，选择第 $p$ 部电梯服务乘客 $r$。若这部电梯上一次服务编号为 $l$，转移增加

$$g_{p,l,r}\cdot |y_l-x_r|+A_{day_r}\cdot|x_r-y_r|.$$

第一项是空载调整位置的最小费用，第二项是当天必须支付的载客移动费用。把第 $p$ 个最后服务编号改为 $r$ 并取最小值即可。

正确性证明

固定某部电梯相邻两次服务后，其起点与终点均已确定。在这段日期内，空载移动总距离至少为两楼层之差；把全部移动集中到该电梯开启且电价最低的一天恰好达到这个下界，因此预处理的转移费用最优。DP 枚举当前乘客使用的全部三种电梯，并保留每种最后服务状态的最小费用，所以没有遗漏任何合法服务分配。按乘客顺序归纳，所有状态值均为对应状态的最优费用，最终最小值即全局最优答案。

复杂度

满分算法时间复杂度为 $O(Q^3)$，空间复杂度为 $O(Q^2)$；中档算法时间复杂度为 $O(Q^4)$；小档算法为指数复杂度。