@[tyh18696696627](/user/705729)
~~这道题目其实是我们老师给我们考试题的弱化版~~
```c
#include <bits/stdc++.h>
using namespace std;
char a[100010],b[100010],x;
int dp[2][100010],len=0,now=0,last=1;
int main(){
while(cin>>x){
len++;
a[len]=x;
b[len]=a[len];
}
reverse(b+1,b+len+1);
memset(dp,0,sizeof(dp));
int maxs=0;
for(int i=1;i<=len;i++){
swap(now,last);
for(int j=1;j<=len;j++){
if(a[i]==b[j]) dp[now][j]=dp[last][j-1]+1;
else dp[now][j]=max(dp[last][j],dp[now][j-1]);
}
}
cout<<len-dp[now][len];
return 0;
}
```
我是用了滚动数组来优化的，其实也不用；只不过我们老师的那道题目，l<=1e5。
by zjinze @ 2023-08-22 16:58:45
_打错了，是l<=1e4_
by zjinze @ 2023-08-22 20:56:00