題意：給你一個包含大小寫及數(shù)字的字符串，要求出把該字符串變?yōu)榛匚牡闹辽僖砑訋讉€字母。
解法：想到了翻轉(zhuǎn)字符串，然后求LCS，沒想到用字符串的長度減去LCS的長度就是結(jié)果(這個很容易證明)。因為字符串長度有5000所以要用滾動數(shù)組，不然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;
}