一、题目大意
一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。
设原序列S的逆序列为S’ ，则这道题目的关键在于，
最少需要补充的字母数 = 原序列S的长度 — S和S’的最长公共子串长度
于是看似一个回文字串，变成了LCS。但是关键是这个不能用裸的LCS搞定，因为5000的int二维数组，大约100M，肯定爆64M的内存。
要用到滚动数组，思路如下：
因为找子串的时候是一排一排刷的，而关系到的排只会是上一排，这样就只用保存2排就好（交替使用）。
二、AC code
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <cassert>
#include <time.h>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <sstream>
#define INF 0x3f3f3f3fusing namespace std;template <class Type>
Type stringToNum(const string& str)
{istringstream iss(str);Type num;iss >> num;return num;
}//======================================================#define MAXN 5002int dp[2][MAXN]; //两排int whLCS(char s1[],int len1,char s2[],int len2) {int rowFlag = 1;for(int i=1;i<=len1;++i) {for (int j=1;j<=len2;++j) {if(s1[i-1]==s2[j-1])//dp[i][j]=dp[i-1][j-1]+1;dp[rowFlag][j]=dp[!rowFlag][j-1]+1;elsedp[rowFlag][j]=max(dp[!rowFlag][j],dp[rowFlag][j-1]);}rowFlag = !rowFlag;}return dp[!rowFlag][len2];
}int main()
{//freopen("input.txt","r",stdin);int n;cin>>n;char input[MAXN];char reverse[MAXN];getchar();int i;for (i=0;i<n;++i){cin>>input[i];reverse[n-1-i]=input[i];}input[i]='\0';reverse[i]='\0';int res = whLCS(input,strlen(input),reverse,strlen(reverse));cout<<strlen(input) - res<<endl;return 0;
}三、网上好文
先看看几种不同的申请空间方法的区别：
静态数组 开销大小为5001*5001的int是铁定超的.
据说用short int的话不会MLE，有兴趣的同学可以试试动态数组 单纯的申请动态数组是不能解决这个问题的，动态数组只能增加空间利用率，
但是本题最恶劣的数组大小还是5001*5001，动态数组是不能改变这个事实的滚动数组 这里重点讲一下滚动数组在这个题目中的应用.自己目前理解的应用滚动数组的目的就是减少空间开销.首先可以在纸上简单模拟一下DP的转移过程.确定好最少行数或者列数之后,重点就是在如何进行”滚动”以及如何用表达式控制这个滚动.
对于本题,我用的是行数以0–1–0–1的滚动方式，滚动表达式为i%2和(i-1)%2 ，没错，就是强大的求余滚动O(∩_∩)O