P14730 [ICPC 2022 Seoul R] Palindrome Type

Refrained · 2025-12-13 11:35:44 · 题解

签到题。

1. 题目分析

简单递归，两边向中心收缩，同时设置阈值 d，递归过程中保证 d<k 才继续递归，这样复杂度将会控制在 O(2^k n) 以内。

2. 代码

#include<bits/stdc++.h>
using namespace std;
string s;
bool check(int l,int r,int d,int dep)
{
    while(l<=r&&s[l]==s[r])l++,r--;
    if(l>=r)return true;
    if(d>=dep)return false;
    return check(l+1,r,d+1,dep)||check(l,r-1,d+1,dep);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>s;
    for(int k=0;k<=3;k++)if(check(0,s.size()-1,0,k))return cout<<k<<"\n",0;
    cout<<"-1\n";
    return 0;
}