题目地址 http://poj.org/problem?id=1159
就是给你一个字符串，添加最少的字符使得其变成一个回文串
我不太懂DP，于是就搞来了这么一道大水题..
zzz许久后，我想到了只要把正中间两边的字符统计一下看有几个不同就可以了..
然而我举出了反例..我实在没办法了上网找题解，发现我思路基本是对的，只要再考虑到顺序问题就可以了
其实这就是个LCS!!!
Orz...
[code lang="cpp"]
/*Source Code

Problem: 1159 User: aclolicon
Memory: 1112K Time: 1469MS
Language: G++ Result: Accepted
Source Code*/
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char s[55550];
char r[55550];
int dp[2][50500];
int n;
int main(){
cin >> n;
cin >> s;
int cnt = 0;
memset(dp, 0, sizeof(dp));
for (int i = n - 1; i >= 0; i--) r[cnt++] = s[i];
// cout << r << endl;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++){

if (r[i - 1] == s[j - 1]) dp[i & 1][j] = dp[(i - 1)&1][j - 1] + 1;
else dp[i & 1][j] = max(dp[(i - 1)&1][j], dp[i & 1][j - 1]);
}
cout << n - dp[n & 1][n] << endl;
}
[/code]