蒟蒻的第一篇题解……
dalao勿喷……
题目传送门
我们知道，回文串就是正反读都一样（废话） 所以我们来分析一下一个样例：as3da
对于这一组样例，我们进行如下简（bao）便（li）操作：
as3da->as3daad3sa(接上一个反串）
这个串明显是一个回文串 为了保证这个串始终是一个回文串，我们删除掉这个串前后两个部分中所有 同样位置上相同的部分
步骤如下：
as3da ad3sa ->as3da ad3sa->sd da
我们不难看出，剩余部分是sd的回文串
在原串中，已经存在了串sd，所以我们只需加入ds
即 ads3sda
（其实就是找原串和反串的最长公共子序列）
上代码：
//此题dp的关键就是要想到最长公共子序列
#include <cstdio>
#include <iostream>
using namespace std;
int n,ans,f[5001][5001];//f[i][j]为s数组的前i个数与k数组前j个个数所组成的最长子序列
char s[5001],k[5001];
int main()
{
scanf("%d\n",&n);
for(int i=1; i<=n; i++)s[i]=getchar(),k [n-i+1]=s[i];
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(s[i]==k[j])
{//如果子序列还能继续
f[i][j]=f[i-1][j-1]+1;
}
else f[i][j]=max(f[i-1][j],f[i][j-1]);
}
}
printf("%d",n-f[n][n]);
return 0;
}
