题意：给你一个包含大小写及数字的字符串，要求出把该字符串变为回文的至少要添加几个字母。
解法：想到了翻转字符串，然后求LCS，没想到用字符串的长度减去LCS的长度就是结果(这个很容易证明)。因为字符串长度有5000所以要用滚动数组，不然MLE。
#include <stdio.h>
#include <string.h>
#define N 5005
#define MAX(a, b) (a > b ? a : b)
char s1[N], s2[N];
int a[N], b[N];
int main()
{
int n;
while(~scanf("%d", &n))
{
scanf("%s", &s1);
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(int i = 0; i < n; i++)
s2[i] = s1[n - i - 1];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(s1[i] == s2[j])
{
b[j + 1] = a[j] + 1;
}
else
{
b[j + 1] = MAX(b[j], MAX(a[j], a[j + 1]));
}
}
for(int j = 0; j <= n; j++)
{
a[j] = b[j];
b[j] = 0;
}
}
printf("%d\n", n - a[n]);
}
return 0;
}