自动搬运

查看原文

来自洛谷，原作者为

	BYR_KKK **

搬运于2025-08-24 23:11:52，当前版本为作者最后更新于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)$。