记 f i f_i fi 为 i i i 时刻发车,处理完等车时间 ≤ i \le i ≤i 的学生的最小花费。
线性 dp。考虑枚举分界点 j j j,将 j + 1 j+1 j+1 到 i i i 的学生打包在 i i i 时刻送走,花费为 ∑ i − t x \sum i - t_x ∑i−tx,其中 t x t_x tx 在 j + 1 j+1 j+1 到 i i i 之间。时间复杂度 O ( T 2 ) O(T^2) O(T2)。代码
注意到 j + 1 j+1 j+1 到 i i i 超过 2 m 2m 2m 可以再次分段。 时间复杂度 O ( m T ) O(mT) O(mT)。代码。