自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 22:23:02，当前版本为作者最后更新于2024-01-25 13:48:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

被 QOJ1193 Ambiguous Encoding 撞了。

考虑直接 dp，设 $f_{i, j}$ 为较长的串未被较短的串覆盖的部分是第 $i$ 个字符串的长为 $j$ 的后缀。转移考虑枚举接在较短的串后面是第 $k$ 个串，然后讨论一下 $j$ 和第 $k$ 个字符串的大小关系就可以确定转移到哪。

发现转移成环，考虑建图用最短路转移。这里 $|E| = n^2m, |V| = nm$，复杂度看似是 $O(|E| \log |V|) = O(n^2m \log nm)$ 的。但是 Dijkstra 最短路复杂度中的 $|E|$ 实际上是松弛次数，但是这题考虑最大边权 $\le m$ 所以任意时刻队列距离的极差 $\le m$，所以每个点松弛次数 $\le m$，所以复杂度其实是 $O(n^2m + nm^2 \log nm)$。这可以解释为什么 QOJ1193 Ambiguous Encoding 跑得那么快。

code