最短回文串(palindrome)
【问题描述】
如果一个字符串正过来读和倒过来读是一样的,那么这个字符串就被称作回文串。例如abcdcba,abcddbca就是回文串,而abcdabcd不是。
你要解决的问题是:对于任意一个字符串,输出将这个字符串变为回文串需要插入的最少字符个数,比如,ab3bd只需要插入2个字符就可以变为一个回文串。
【输入格式】
第一行是一个整数N
第二行是一个长度为N字符串S
【输出格式】
一行一个整数,表示将S变为回文串需要插入的最小字符个数
【输入样例 】
5
ab3bd
【输出样例】
2
【数据范围 】
对于所有数据,0<n<=5000
思路一:
设f(i,j)为将Ai..Aj变为回文串的最小代价,则
一共有n^2个状态,状态转移是O(1)的,总的复杂度为O(n^2)
for(int i=n; i>0; i--)
for(int j=i+1; j<=n; j++)
if (a[i]==a[j]) f[i][j]= f[i+1][j-1];
else
f[i][j]=min(f[i+1][j], f[i][j-1])+1;
cout<< f[1][n]<< endl;
思路二:
将原串与原串的倒序做一次LCS—最长公共子序列,用原串长度减去LCS长度,即为需要插入字符的个数
例如:ab3bd与 db3ba
LCS(‘ab3bd’, ‘db3ba’)=‘b3b’
因此, ans=Len(‘ab3bd’)-Len(‘b3b’)=2
#include<bits/stdc++.h> using namespace std; void FUCK(string name){ string i=name+".in"; string o=name+".out"; freopen(i.c_str(),"r",stdin); freopen(o.c_str(),"w",stdout); } string a,b,s; int dp[5001][5001],n; int main(){ FUCK("palindrome"); //program here cin>>n>>s; a=b=s; for(int i=0;i<a.size();i++){ b[a.size()-i-1]=a[i]; } dp[0][0]=0; for(int i=1;i<a.size();i++){ for(int j=1;j<b.size();j++){ dp[i][j]=0; if(a[i-1]==b[j-1]){ dp[i][j]=dp[i-1][j-1]+1; } if(dp[i-1][j]>dp[i][j]){ dp[i][j]=dp[i-1][j]; } if(dp[i][j-1]>dp[i][j]){ dp[i][j]=dp[i][j-1]; } } } int hehehe = dp[a.size()-1][b.size()-1]; cout<<a.size()-hehehe<<endl; return 0; }