自动搬运

查看原文

来自洛谷，原作者为

	0xyz assign3

搬运于2025-08-24 22:53:26，当前版本为作者最后更新于2023-12-23 18:36:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

赛后写出，比 std 少一个 $\log$，不需要任何数据结构。

不难想到区间 DP，令 $f_{i,j}$ 表示将区间 $[i,j]$ 完全折好最少要折多少次，以及在这一前提下最小的不对称度是多少。那么我们枚举在哪个点 $k$ 折叠，并转移即可。能在点 $k$ 折叠要求 $k$ 左右边能完全匹配的位数 $p_k\ge\min(k-i,j-k)$。这个 $p_k$ 可以 $O(n^2)$ 预处理。总时间复杂度 $O(n^3)$ 的代码。

考虑优化，注意到对于区间的左半边是一类转移，区间的右半边是一类转移。对于剩余串 $a$ 和 $b$，如果 $b$ 是 $a$ 的子串，那么 $b$ 的最优折叠一定优于 $a$ 的最优折叠。这启示我们，对于区间 $[i,j]$ 左半边的所有 $k$，取最右边那个，设为 $s$；右半边的，取最左边那个，设为 $t$。$f_{i,j}$ 只需要由 $f_{s+1,j}$ 和 $f_{i,t-1}$ 转移而来，这样就可以保证每次操作都是最优的。代码。

注意到 $s$ 的实质是前缀 $[1,\lfloor\frac{i+j}{2}\rfloor]$ 里满足 $i\ge k-p_k$ 的最大 $k$。状态 $(\lfloor\frac{i+j}{2}\rfloor,i)$ 只有 $O(n^2)$ 个，所以我们可以通过枚举 $O(n^2)$ 预处理出所有 $s$。对 $t$ 的处理同理。总时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$，跑得很快。代码。