题目意思是最少加多少个字母，使得原字符串变成回文串。
可以用经典的LCS思想来解决此问题，因为若一个字符串，其反串和自身的LCS就等于自身的长度，那么该串必为回文串。因此，对给定字符串求反，然后求双方的LCS，所得的长度，就是不用添加字符的最长子串。那么要添加的字符数目，就是：
ans=原字符串长度-LCS(String,revString);
可以自己动手画画，很好理解的。由于此题数据规模很大，二维的数组是不行的，要用滚动数组。
以下是代码 ：
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int max(int a,int b) {return a>b?a:b;} const int N=5010; int c[N],d[N]; char str[N],str1[N],str2[N]; int n; void LCS() { int i,j; for(i=1;i<=n;i++) { memcpy(d,c,sizeof(c)); memset(c,0,sizeof(c)); for(j=1;j<=n;j++) { if(str1[i]==str2[j]) c[j]=d[j-1]+1; else c[j]=max(c[j-1],d[j]); } } } int main() { while(scanf("%d",&n)==1) { scanf("%s",str); int i,j=1; for(i=0;i<n;i++) str1[i+1]=str[i]; str1[i+1]='/0'; for(i=n-1;i>=0;i--) str2[j++]=str[i]; str2[j]='/0'; memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); LCS(); printf("%d/n",n-c[n]); } return 0; }
