Problem Address：http://poj.org/problem?id=1159
事实上是一道LCS，不过做了一点点修改而已。
算是第一次打LCS，不过居然一次AC了，而且各种数据都还不赖。
时间上虽然不是最好。
思路就是将字符串反转过来，找出前后两个字符串的LCS，将字符串的长度减去LCS的值就得到答案。
原来的LCS需要n*n的空间存储数据，由于不需要记录路径，所以我直接改成两个一维数组记录，节省了大量空间。
搜了一下看到有人MLE的，庆幸= =
以下贴代码：
#include <iostream>
using namespace std;
int main()
{
char s[5005],t[5005];
int d[5005],p[5005],n,i,j;
scanf("%d", &n);
scanf("%s", s);
for (i=n-1,j=0; i>=0; i--,j++)
{
t[j] = s[i];
}
for (i=0; i<n; i++)
{
d[i]=0;
p[i]=0;
}
for (i=0; i<n; i++)
{
if (i%2==0)
{
if (t[i]==s[0]) d[0]=1>p[0]?1:p[0];
else d[0]=p[0];
for (j=1; j<n; j++)
{
if (t[i]==s[j])
{
d[j] = p[j-1]+1>p[j]?p[j-1]+1:p[j];
}
else
{
d[j] = d[j-1]>p[j]?d[j-1]:p[j];//这里可能是错的，可能是d[j]=0
}
}
}
else
{
if (t[i]==s[0]) p[0]=1>d[0]?1:d[0];
else p[0]=d[0];
for (j=1; j<n; j++)
{
if (t[i]==s[j])
{
p[j] = d[j-1]+1>d[j]?d[j-1]+1:d[j];
}
else
{
p[j] = p[j-1]>d[j]?p[j-1]:d[j];//这里可能是错的，可能是p[j]=0
}
}
}
}
printf("%d/n", n-(d[n-1]>p[n-1]?d[n-1]:p[n-1]));
return 0;
}
加油加油！！！