Codeforces 1007 E. Mini Metro 2024-07-01 14:46 folder 题解

太牛。

最波特的地方：添加一个永远有无穷多人的站台在最后，这样每次都会恰好带走 k 个人。

开始魔怔 DP。fi,j 表示前 i 个站台，要撑 j 单位时间，最少需要召唤的火车数量；gi,j 表示前 i 个站台，要撑 j 单位时间，且清空 1,2,…,i−1 的站台，最少需要召唤的火车的数量。以上都要求每趟火车都恰好带走了 k 个人。

于是我们有初值 f0,j=g0,j=0，答案是 fn,t。

接下来考虑转移。

若前 j 个时刻没有任何火车带走站台 i 的人，也就是说 ai+j⋅bi≤ci 且 fi−1,j<+∞。此时用 fi−1,j 直接更新 fi,j。

然后考虑 gi,j，它的值有下界 ⌈∑u<i(au+j⋅bu)/k⌉。注意到我们只需要保证这么多趟火车带走的人不超过 ∑u≤i(au+j⋅bu) 就一定能构造出方案。

因为我们已经在前 j 个时刻有每次都恰好带走 k 个人的方案，所以我们只需要在 j 时刻继续带走剩下的人即可。

若前 j 个时刻有火车带走站台 i 的人。设最后一次是在第 r 个时刻。那么，当时一定也清空了前 i−1 个站台，至少要花 gi,r 趟火车。

设当时第 i 个站台还有 rem=∑u≤i(au+r⋅bu)−k⋅gi,r 个人，那么它最后会变成 rem+(j−r)⋅bi 个人。

为了避免以后爆炸，我们需要考虑先接走 ⌈max(rem+(j−r)⋅bi−ci,0)/k⌉ 个人，当然前提是可行。

那么，接下来，就是对前 i−1 个站台重新开始游戏，但此时初始的 au 变成了 0。因此我们对于初始为 ai 和 0 分别做一次 DP 即可。此时 gi,j 的转移是类似的。

时间复杂度 O(nt2)。