AcWing 1222. 密码脱落(最长公共子序列,露头就秒)
原题链接
中等
作者:
羡笙雨
,
2024-03-29 19:41:09
,
所有人可见
,
阅读 8
#include<bits/stdc++.h>
using namespace std;
char a[1005];
char b[1005];
const int N=1005;
int f[N][N];
int main()
{
cin>>a+1;
memcpy(b,a,sizeof a);
reverse(a+1,a+1+strlen(a+1));
int n=strlen(a+1);
// cout<<strlen(b+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
else
f[i][j]=max(f[i][j],f[i-1][j-1]);
}
}
cout<<n-f[n][n]<<endl;
return 0;
}