题目大意：

回文是一个对称的字符串，即从左到右以及从右到左读取相同的字符串。你要写一个程序，给定一个字符串，确定插入字符串中的最小字符数，以便获得回文。例如，通过插入2个字符，字符串“ab3bd”可以转换为回文（“dab3bad”或“adb3bda”）。但是，插入少于2个字符不会产生回文。

输入

您的程序将从标准输入中读取。第一行包含一个整数：输入字符串n的长度，3<=n<=5000。第二行包含一个长度为n的字符串。该字符串由从“a”到“z”的大写字母、从“a”到“z”的小写字母以及从“0”到“9”的数字组成。大写字母和小写字母应视为不同的。

输出

您的程序将写入标准输出。第一行包含一个整数，这是所需的最小数。

思路：

求出最长公共子序列ans，然后用n-ans即为所求，而开dp[5000][5000] 数组会超限，所以开一个滚动数组。

Code：

#include <iostream>
#include <cstdio>
#include<cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int ll;
char a[5007],s[5007];
int dp[2][5007];
int main()
{int n;while(~scanf("%d",&n)){int i,j,k=0;getchar();memset(dp,0,sizeof(0));for(i=0;i<n;i++)scanf("%c",&a[i]);for(i=n-1;i>=0;i--)s[k++]=a[i];      //反向存串int m=n;for(i=0;i<n;i++)       //经典最长公共子序列{for(j=0;j<m;j++){if(a[i]==s[j])dp[(i+1)%2][j+1]=dp[i%2][j]+1;elsedp[(i+1)%2][j+1]=max(dp[i%2][j+1],dp[(i+1)%2][j]);}}printf("%d\n",n-dp[n%2][n]);}return 0;
}