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