Description
回文词是一种对称的字符串——也就是说，一个回文词，从左 到右读和从右到左读得到的结果是一样的。任意给定一个字符串， 通过插入若干字符，都可以变成一个回文词。你的任务是写一个程 序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文 词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。
Input
第一行包含一个整数N，表示给定字符串的长度，3< =N< =5000 第二行是一个长度为N的字符串，字符串由大小写字母和数字 构成。
Output
一个整数，表示需要插入的最少字符数。
Sample Input
5
Ab3bd
Sample Output
2题目分析：
首先要把原字符串反转，制造对称字符串。之后就是找两个字符串的LCS
首先，定义f[i][j]表示原字符串到i，新字符串到j时的LCS。
当a[i]==b[j]时f[i][j]=f[i–1][j–1]+1
当a[i]!=b[j]时f[i][j]=max(f[i][j–1],f[i–1][j])
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
char s[6000],p[6000];
int n;
int f[5100][5100];
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=n;i++) p[i]=s[n-i+1];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(p[i]==s[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;
}