蒟蒻的第一篇题解……
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; }