题解：P14730 [ICPC 2022 Seoul R] Palindrome Type

P14730 [ICPC 2022 Seoul R] Palindrome Type 题解

---

纯享阅读区
题目传送门

总体分析

核心：修改字符串 $s$ 使其成为回文串，记最小次数为 $k$，如果 $k\leq3$，输出 $k$，否则输出 -1 。

因此，可以从 $k=0\sim3$ 依次进行 DFS 搜索，只要有一次成功，输出 $k$，结束。

思路引导

提问
如何 DFS 搜索修改过程算出 $k$？

DFS 函数
使用 双指针。

当 $l<r$ 时：

• 如果左指针 $l$ 和右指针 $r$ 对应的 $s_l=s_r$，那么这部分已经是回文的，$l$ 向右移，$r$ 向左移。
• 否则：
  • 如果剩余次数 $step=0$，无法继续修改，返回无法完成。
  • 如果删除 $l+1$ 或 $r+1$ 可完成，返回可以完成。
  • 否则返回无法完成。

返回无法完成。

警告
如果 $k\leq 3$ 都不可以，最后输出 -1 。

核心代码

bool dfs(int l, int r, int step){

    while(l<r){
        if(s[l]==s[r])l++,r--;
        else{
            if(!step)return 0;
            if(dfs(l+1,r,step-1)||dfs(l,r-1,step-1))return 1;
            return 0;
        }
    }
    return 1;

}