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;}
加油加油！！！
