回文字串
解题思路
突破口：回文串特性，正着读反着读都一样
转化成求最长公共自序列的问题
正序与倒序“公共”的部分就是我们回文的部分，如果把正序与倒序公共的部分减去你就会惊奇的发现剩余的字符就是你所要添加的字符，也就是所求的正解
分析样例：ab3bd，样例倒序：db3ba
把ad，da加起来成回文串就是adb3bda，所以这个问题就可以转化成了求最长公共自序列的问题，将字符串的长度减去它本身的“回文的”（最长公共自序列）字符便是正解
具体实现
最长公共自序列问题是个经典的dp问题，
最容易想到的方法就是开个二维数组dp【i】【j】，i，j分别代表两种状态；
那么我们的动态转移方程应该就是if(str1[i] == str2[j]) dp[i][j]=dp[i-1][j-1]+1;
Else dp[i][j] = max(dp[i-1][j], dp[i][j-1];依此即可解出最长公共自序列，用字符串长度减去即是正解
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
using namespace std;
int n;
int dp[5001][5001];
char str1[5001],str2[5001];
int main()
{
scanf("%s", str1+1);
n = strlen(str1+1);
for(int i = 1; i <= n; i++)
str2[i] = str1[n-i+1]; //做一个逆序的字符串数组
for(int i = 1; i<=n; i++)
for(int j = 1; j <= n; j++)
if(str1[i] == str2[j])
dp[i][j] = dp[i-1][j-1] + 1; //最长公共自序列匹配
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]); //不匹配的往下匹配状态
printf("%d\n", n-dp[n][n]); //字符串长度减去匹配出的最长公共自序列的值
return 0; //即需要添加的字符数
}可这并不是最优解法，只是能ac这道题而已 若是将内存限制改为2MB呢？
不过，没关系，正常开一个5001*5001的数组一定会爆掉的，此时你是不是在思考另一种解决方案来优化一下空间复杂度，如果我可以把它用一维数组代替二维数组中的状态量是不是也可以求出正解
没错。它真的能求出正解；
如果你仔细研究一下就会发现每次搜索到str1的第i个元素的时候，数组dp【】【】真正使用到的元素仅仅是dp【i】【j】和dp【i-1】【k】（0 <= k <= n(n = strlen(str1)）
即dp【】【】的第一下标从0–>i-2就没有用处了，因此我们可以开辟两个滚动数组来降低空间复杂度
Dp1【】用来记录当前状态，dp2【】用来记录之前的状态也就相当于刚才的dp【i-1】【j】
动态转移方程应该这么表达if(str1[i] == str2[i]) dp1[j] = dp2[j-1] +1;
Else dp1[j] = max(dp1[j-1], dp2[j]);
源代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
using namespace std;
int n;
int dp1[5001],dp2[5001]; //此处用两个滚动数组记录，一个记录之前的状态，一个记录此时的状态
char str1[5001],str2[5001];
int main()
{
//freopen("palindrome.in", "r", stdin);
//freopen("palindrome.out", "w", stdout);
scanf("%s", str1+1);
n = strlen(str1+1);
for(int i = 1; i <= n; i++)
str2[i] = str1[n-i+1]; //做一个逆序的字符串数组
for(int i = 1; i<=n; i++)
{
for(int j = 1; j <= n; j++)
if(str1[i] == str2[j])
dp1[j] = dp2[j-1]+1; //“发现”匹配就记录
else
dp1[j] = max(dp1[j-1],dp2[j]); //不匹配就匹配后面的状态
memcpy(dp2, dp1, sizeof(dp1)); //记录之前的状态“滚动”匹配
}
printf("%d\n", n-dp1[n]); //字符串长度减去匹配出的最长公共自序列的值
return 0; //即需要添加的字符数
}竞赛中常见状态说明
AC: Accept 通过
出现这个图标的时候表示在本测试点中你的输出是正确的，拿到了本测试点的满分
WA: Wrong Answer 答案错误
出现这个图标的时候表示在本测试点中你的输出是错误的，在本测试点中未拿到任何分数
RE: Runtime Error 运行时错误
这表明你的程序在运行过程中因为出锅而崩溃了，通常可能是访问非法内存等问题，出现这个提示但你还能过样例的话，大概率是数组没开够，仔细检查一下。
CE: Complie Error 编译错误
这表明你的程序没有通过编译。如果在本地编译可以通过的话，检查一下提交语言是不是选对了或是有没有引用一些不该引用的东西
TLE: Time Limit Exceeded 超出时间限制
这表明你的程序运行所用的时间超过了测试点的规定时间。出现这个提示时一般表明你的算法的时间复杂度不够优秀，需要优化；但也有可能程序深入死循环无法自拔
MLE: Memory Limit Exceeded 超出内存限制
这表明你的程序所调用的内存大小超出了测试点的内存限制，一般表明你的算法的空间复杂度不是很优秀，比如像NOIP铺地毯中什么百万级二维数组的失智做法什么的，好好优化一下~
PC: Partially Correct 部分正确
这个提示信息一般会在题目启用Special Judge的时候可能会返回，代表着你得到了本测试点的部分分数。一般情况有两个：
- 你的答案正确，格式错误，Special Judge给你送了点良心分
- 你的答案中间有一部分是正确的，根据题目要求，Special Judge 给你返回了你这一部分答案的分数
这个时候一定要仔细查看Special Judge 给你返回的信息，仔细检查，距离AC就不远啦！
OLE: Output Limit Exceeded 超出输出限制
表示你的程序出现了 大 量 的输出，一般还是程序在输出过程中深陷死循环无法自拔，好好检查一下代码逻辑~
UKE: Unknown Error 未知错误
这个时候一般是评测姬锅了，如果多次提交都是出现这个提示的话，赶快联系网站的管理员鸭~
文章引用
