1159

 

/*
回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字，都可以变成回文词
此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。
 每当遇到一个题目就要分析它的特点。对于这个题目来说，我们设所给的字符串是串s=a1a1...an,我们的目的是通过在S上添加尽量少的字母使其达到回文的要求，我们设这种添加最少的字符之后形成的回文字符串是S'=b1b2...b(n+m),我们所求的这个最小数就是m
在字符串 s'里有bi=b(n+m-i+1)。
那么我们就得找s中的这两类字符串：
A:s'中与此类字符串对称的字符出现在s'-s中
B:s'中与此类字符串对称的字符出现在s中
看这个例子
把Ab3bd扩充成
d  A  b  3  b  A  d（红色的字母是添加的）
1  2  3  4  5  6   7
位置2，7的对称位置的字符不属于S，
故A={2, 7}
位置3，4，5的对称位置的字符属于S，
故B={3, 4, 5}
这两类字符串的数量和是n,其中A类字符的数量(用|A|表示)就是我们所求的，而我们可以通过n-|B|求得，那么我们的目标就是找|B|了，B字符串有什么特点呢？就是B本身就是一个回文串，回文串又有什么特点呢？就是回文串B是字符串S和它的反向串的LCS（最长公共子串），那么就把这个问题转化成了求LCS的动态规划问题。
*/  

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

char  a[5001];
short d[2][5002];
int main()
{
 #ifdef LOCAL
 freopen("data.in","r",stdin);
 freopen("data.out","w",stdout);
 #endif

 int n;
 char tmp;
 scanf("%d\n%s",&n,a+1);
 memset(d,0,sizeof(d));
 for(int i=1;i<=n;i++)
 for(int j=n;j>=1;j--)
 if(a[i]==a[j])
   d[i%2][j] = d[(i-1)%2][j+1]+1;
 else
   d[i%2][j] = max(d[i%2][j+1],d[(i-1)%2][j]);
    cout< return 0;
}