自动搬运

查看原文

来自洛谷，原作者为

	HP_Serenity 不拿7勾不改签

搬运于2025-08-24 23:15:20，当前版本为作者最后更新于2025-05-17 13:08:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第一次场蓝，写篇题解纪念下。

关于符号的说明：$\operatorname{and}$ 代表按位与。

给定一个长度为 $n$ 的序列 $x$ 和一个初始位置 $a=p$，每次操作可将 $a$ 移至任意位置，而第 $j$ 次操作花费为 $w_{i,j}+2 \times (L-(x_a \operatorname{and} x_i))$。$L$ 为序列 $x$ 的最大值，目标是求出第 $k$ 次操作结束时，将 $a$ 转移到每个位置 $i$ 的最小总花费。

考虑 dp 做法。定义 $dp_{i,j}$ 为 $j$ 次操作后 $a$ 位于位置 $i$ 的最小总花费。因为在 $j$ 次操作时可以从任意位置 $v$ 移到 $u$，所以令 $w_{i,j}$ 为第 $j$ 次操作转移到 $u$ 的花费，推出动态转移方程：

$ dp_{j,u}=\displaystyle\min_{1 \le i \le n} (dp_{j-1,v}+w_{u,j}+2 \times (L-x_v \operatorname{and} x_u)) $。

但是时间复杂度为 $O(n^2 \times k)$，显然超时。

观察到 $0 \le x_i < 2^{16}$，考虑位运算优化。将 $x_i$ 拆成高低 $8$ 位。令 $high_i=(\lfloor\frac{x_i}{2^8} \rfloor) \operatorname{and} (2^8-1)$ 而 $low_i=x_i \operatorname{and} (2^8-1)$。根据按位与的性质，可将 dp 式子拆成高低 $8$ 位的贡献，即

$ dp_{j,u}=\displaystyle\min_{1 \le i \le n} (dp_{j-1,v}+w_{u,j}+2 \times L-2 \times (high_v \operatorname{and} high_u) \times 256-2 \times (low_v \operatorname{and} low_u)) $。

最后再通过预处理最小值进一步优化即可。

记 $P$ 为 $2^{24}$，则时间复杂度：$O(k \times P)$。空间复杂度：$O(n \times k)$。可以通过。

AC 记录，代码。