题解【CF1363F Rotating Substrings】

UperFicial · 2022-09-28 08:51:56 · 题解

CF1363F Rotating Substrings *2600

解题报告。

不一定更好的阅读体验。

感觉楼上的 DP 状态设计与 DP 转移方程的联系是说不通的，有些地方没有讲明白，所以这篇题解就详细讲一下。

首先，一次操作的本质是，将一个 S 的一个字符插到前面的某一个位置。

判 -1 是容易的，即对于任意一个字符 c，在 S 中的出现次数和 T 中的出现次数是相等的。

那么我们就可以设 f_{i,j} 表示将 S 的长度为 i 的前缀，插入最少几个字符，使得和 T 的长度为 j 的前缀相同。显然这里 i,j 的大小关系为 i\le j。

考虑 f_{i,j} 的转移，首先，我们可以不让 s 的前缀 i 和 t 的前缀 j 匹配，而是让 s 的前缀 i 和 t 的前缀 (j-1) 进行匹配，这时候会多出一个 s_j 没有匹配。我们让 i 之后的某一个 s_k=t_j 的字符 s_k 向前移动到 i 的前面，与 s_j 进行匹配，花费为 1。注意，这里一定会找到一个合法的 s_k，因为每一个字符都是两两配对的。于是我们有状态转移方程 f_{i,j}=f_{i,j-1}+1。

其次是比较简单的 case，若 s_i=t_j，那么可以通过 f_{i-1,j-1} 来继承。f_{i,j}=f_{i-1,j-1}。

最后一种情况，设 x 表示 s_i 在 S 的前缀 i 中出现次数，y 表示 s_i 在 T 的前缀 j 中出现次数。

若 x\le y 说明了什么？考虑 f_{i-1,j}，S 的前缀 (i-1) 与 T 的前缀 j 中 s_i 的数量 x',y 一定满足 x'<y。这也就说明，要想完成 (i-1) 和 j 的匹配，就必须至少把 s_i 移动到前面。然后再移动若干字符。把 s_i 移动到前面后再插入若干字符本质上是前缀 i 与 j 进行匹配，也就是 f_{i,j} 的值，所以这个部分就直接继承：f_{i,j}=f_{i-1,j}。