CF1701E 题解

EuphoricStar · 2022-07-16 11:14:06 · 题解

思路

手玩几组数据可知：

• 若不回到开头删字符，则操作次数为 n - pl，其中 pl 表示 s 和 t 的 \mathrm{LCP} 长度。

• 若需要回到开头删字符，则最优解一定是光标先从右往左移动一段，若有不同的字符则按一次 backspace；然后按 home 回到开头，光标从左往右移动一段，若有不同的字符则需要先按 right 再按 backspace。中间有一段是跟 t 中相同长度的一段匹配的，因此不用动。

可以把 s 分成前、中、后三部分，然后 dp。设 f_{i,j,0/1/2} 表示当前处理到 s 的第 i 个字符，跟 t 中前 j 个字符匹配，当前光标在前/中/后部分的最少移动次数。

转移：

• 任意时刻，若光标在前/后部分，都可以删除当前字符。在前部分删除一个字符的代价是 2（因为要先按 right 再按 backspace），在后部分删除一个字符的代价是 1。因此：

注意这里没有 f_{i,j,1} 的转移，是因为中部分的字符不能修改。

• 当 s_i = t_j，若光标在前/后部分，则直接按 right/left，匹配长度增加 1。若光标在中部分，则直接沿用之前的值。因此：

• 任意时刻，光标都可以从前部分转入中部分/后部分，或从中部分转入后部分。因此：

注意最后还要加上按 home 的操作，即操作次数为 f_{n,m,2}+1。

由于此题卡空间，所以要用滚动数组优化。

代码

code