A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome.
As an example, by inserting 2 characters, the string “Ab3bd” can be transformed into a palindrome (“dAb3bAd” or “Adb3bdA”). However, inserting fewer than 2 characters does not produce a palindrome.
这道题的意思就是求最少补多少个字符使所给字符串变成回文 求最长回文子序列经典做法 反转目标串求lcs
#include<iostream> using namespace std; #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<stdlib.h> #include<vector> #include<queue> #include<deque> #include<map> #include<set> #include<time.h> #define pi(x,y) printf("%d%c",(x),(y)); #define pin(x) printf("%d\n",(x)); #define si(x) scanf("%d",&(x)) #define sii(x,y) scanf("%d%d",&(x),&(y)) #define s3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define rep(x,y,z) for(int (x)=(y);(x)<(z);++(x)) #define dep(x,y,z) for(int (x)=(y)-1;(x)>=(z);--(x)) #define read int TcaseN;scanf("%d",&TcaseN);for(int Tcase=1;Tcase<=TcaseN;++Tcase) #define cls(x,y) memset((x),(y),sizeof((x))); #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define max3(value_a,value_b,value_c) max(max(value_a,value_b),value_c) #define min3(value_a,value_b,value_c) min(min(value_a,value_b),value_c) #define GT(x) (x)=clock(); #define fin(x) freopen(x,"r",stdin); #define fout(x) freopen(x,"w",stdout); ///In This You Can Define Long Integer Type #define LONGTYPE long long typedef LONGTYPE LL; typedef unsigned LONGTYPE ULL; const int maxint=((~((unsigned)(0)))>>1); const LL maxll=((~((unsigned LONGTYPE)(0)))>>1); const int inf=0x3f3f3f3f; const double PI=acos(-1.0); const int N=5005; char a[N]; char b[N]; int dp[2][N]; int n; int Lcs(){ memset(dp,0,sizeof(dp)); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if(a[i]==b[j]) dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-1]+1); else dp[i&1][j]=max(dp[i&1][j],max(dp[(i-1)&1][j],dp[i&1][j-1])); } } return dp[n&1][n]; } int main() { #ifdef tangge clock_t tSTART,tEND,t3; GT(tSTART); #endif // tangge /*Input:*/ while(scanf("%d",&n)==1){ scanf("%s",a+1); int now=1; memset(b,0,sizeof(b)); for(int i=n;i>=1;--i){ b[now++]=a[i]; } printf("%d\n",n-Lcs()); } #ifdef tangge GT(tEND); printf("%.8lf\n",(tEND-tSTART)/1000.0); #endif // tangge return 0; }