题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1513
解题报告：给定一个长度为n的字符串，在这个字符串中插入最少的字符使得这个字符串成为回文串，求这个最少的个数是多少？
一开始以为只是一个普通的DP题，但是按照我的想法敲出来之后怎么样都W了，无奈搜了解题报告，得知其实这个就是一个最长公共子序列问题，就是求这个字符串跟它的逆序的
字符串的最长公共子序列。因为杭电的题内存都要求在32M内存以内，所以很开心的敲出来才发现10^6的数组都开不了，所以只好寻求空间压缩的方法，一开始就觉得是用滚动数组，但看了很久就是没看出来。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<deque> #include<map> #include<queue> #include<cstdlib> using namespace std; const int maxn = 5005; int dp[2][maxn]; char str[maxn]; int main() { int n; while(scanf("%d",&n)!=EOF) { scanf("%s",str+1); memset(dp,0,sizeof(dp)); int flag = 1; for(int i = 1;i <= n;++i) { flag = !flag; for(int j = 1;j <= n;++j) { if(str[i] == str[n-j+1]) dp[flag][j] = dp[!flag][j-1]+1; else dp[flag][j] = max(dp[!flag][j],dp[flag][j-1]); } } printf("%d\n",n-dp[flag][n]); } return 0; }
HDU 1513 Palindrome（最长公共子序列）,布布扣,bubuko.com
原文：http://www.cnblogs.com/xiaxiaosheng/p/3712650.html
