题解：P11986 [JOIST 2025] 急救车 / Ambulance（暂无数据）

BYR_KKK · 2025-03-29 16:35:01 · 题解

很有意思！

四个点还是太多了，考虑进一步减少限制。若只有 (1,1) 和 (L,L) 两个点应该怎么办？让 C_i 代表 i 到 (1,1) 的成本，D_i 代表 i 到 (L,L) 的成本，此时有 C_i+D_i 为一个常数。因此我们按照 C_i 排序后取一个前缀到 (1,1)，其余点到 (L,L) 即可。

这样我们有一个 O(2^n) 的做法。考虑将所有点分别按照 cost(1,1) 和 cost(1,L) 排序，这样对于每种分组方案而言，存在两个数 b_0 和 b_1，使得只有当 i 按照第一种排序方式后位置 \le b_0 才能选择 (1,1)（否则不能选择 (1,1)，可以选择 (L,L)），按照第二种排序方式后位置 \le b_1 才能选择 (1,L)（否则不能选择 (1,L)，可以选择 (L,1)）。这样如果我们确定了 b_0 和 b_1，那么所有点会被分成四组，每组存在两个选择。

接下来对于每组分别 dp。f_i 代表当该组的第一个选择耗时 i 时第二个选择的最小耗时。这个 dp 的总时间复杂度时 O(nT) 的。对于四组的 dp 全都做完以后，考虑在第一组（两个选择分别为 (1,1) 和 (1,L)）钦定 (1,1) 的耗时，这样能得到 (1,L) 的剩余时间，接着在剩下三组中贪心即可。由于需要枚举 b_0 和 b_1，时间复杂度为 O(n^3T)。无法通过。

实际上我们移动 b_0 和 b_1 的增量只有 1，这意味着每次移动只会带来 O(1) 个点更换组别，我们维护前缀 dp 值和后缀 dp 值可以简单做到 O(n^2T)。