学步园

思路：这个问题可以转换成求LCS 要使最少 则加入的字符的对称位置不可能是加入的字符（即应为原S串中的）
再想一下，就是求S中最长的回文子串（不一定连续）  然后用n - max就是ans

这就成了经典的LCS问题了

//49172K   
782MS

#include <stdio.h>
#define M 5002
short int
c[M][M];    
// 这里用short int 不然超内存了。。。
char s1[M],s2[M];　　　//s1 为原串，s2为倒过来s1
int Max (int a,int b)
{
    return a
> b ? a : b;
}
int DP (int n)  //DP求LCS
{
    int
i,j;
    for (i = 0;i
<= n;i ++)
       
c[0][i] = c[i][0] = 0;
    for (i = 1;i
<= n;i ++)
       
for (j = 1;j <= n;j ++)
       
{
           
if (s1[i] == s2[j])
               
c[i][j] = c[i-1][j-1] + 1;
           
else
               
c[i][j] = Max (c[i-1][j],c[i][j-1]);
       
}
    return
c[n][n];
}
int main ()
{
    int
n,i,k;
    while
(~scanf ("%d",&n))
    {
       
getchar ();
       
gets (s1+1);
       
k = 1;
       
for (i = n;i > 0;i --)
           
s2[k++] = s1[i];
       
int max = DP (n);
       
printf ("%d\n",n-max);
    }
}