AcWing 1222. 密码脱落(区间dp求最长回文子串)(巧妙,可记作模板)
原题链接
中等
作者:
逸误
,
2024-04-04 19:09:48
,
所有人可见
,
阅读 5
//本题可以转换为求i~j之间最长的回文子序列(随意中断的子序列)长度
//区间dp,f[i][j]:考虑i~j区间,其中最长的回文子序列(随意中断的子序列)
//区间dp想思路的时候可以从三四个元素的情况开始想!!
//具体想什么时候能更新过来!
//例如,abba,s[2][3]=2,s[2][4]=2,怎么更新s[1][4]为4?方法:从s[2][3]更新过来!
//要+2就两边一起更新,只更新一边那就不变
//状态划分:f[i][j]根据这一步新增i/j的谁来更新
//f[i+1][j-1]+2:i,j都选取,f[i+1][j],f[i][j-1]:只新增一边,不选取,f[i+1][j-1]:s[i],s[j]不同,都不选取
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1005;
int n;
char str[N];
int f[N][N];
int main()
{
scanf("%s",str+1);
n=strlen(str+1);
for(int len=1;len<=n;len++)//区间dp先枚举长度!
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
if(len==1)
f[l][r]=1;//初始化,一个元素肯定回文
else
{
f[l][r]=max(f[l+1][r],f[l][r-1]);//先只更新一边,不增加回文子串数量(注意这时候没考虑更新数量的情况!)
//上面这行,保证了这个f[l][r]被更新过,后面的dp一定有初始化好的前置条件!
if(str[l]==str[r])//再判断是否满足这个区间能+2的情况
f[l][r]=max(f[l][r],f[l+1][r-1]+2);
}
}
cout<<n-f[1][n]<<endl;
return 0;
}