P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落

本文主要是介绍P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

快速链接

原题链接
题目大意
输入格式
输出格式
数据范围
解题思路
上代码

原题链接

P1435
题目类型： ${\color{yellow} 普及+/提高}$
AC记录：Accepted

题目大意

回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

输入格式

一个字符串。

输出格式

有且只有一个整数，即最少插入字符数

$\mathbf{Sample}$ $\mathbf{Input}$

Ab3bd

$\mathbf{Sample}$ $\mathbf{Output}$

$\mathbf{Hint\&Explain}$
字符串变成dAb3bAd或Adb3bdA。

数据范围

对于 $100\%$ 的数据， $1≤length\le 1000$ 。

解题思路

$d p$ ，就是 $d p$ 。
其实这题看起来难，实际上很简单。
由于要计算回文的关系，首先设原来的字符串为 $a$ ，反转后的字符串为 $b$ ，即如果a="abc"，则b="cba"。如果说，两个字符串里面都有同一个字符，那么这一个字符就不用被记入添加范围。否则，在原来的字符串中要加入一个同样的字符，所以，本题就变成了一个 $\color{red}求最长公共子序列$ 的问题。

求最长公共子序列，无非就是把字符从两个字符串一个一个插入，然后进行动态转移。设 $f_{i,j}$ 为字符串 $a$ 中的前 $i$ 个字符与字符串 $b$ 中的前 $j$ 个字符的最长上升子序列的长度，考虑一下，如果两边插入的字符是一样的，那么就是从在没有插入这两个字符的情况中 $+ 1$ ，即 $f_{i,j}=f_{i-1,j-1}+1$ 。但如果不一样呢？那就要考虑前后顺序了。你可以先插入 $a$ 中，或者先插入 $b$ 中，即 $f_{i,j}=\max(f_{i-1,j},f_{i,j-1})$ 。整理，得：
$f_{i,j}=\begin{cases} f_{i-1,j-1}+1 & a_i=b_j \\ \max(f_{i-1,j},f_{i,j-1}) & a_i\ne b_j \end{cases}$
最后的答案就是 $a.length-f_{a.length,a.length}$ 。

注意：

1.如果说 $a$ 的长度太大，例如 $1\le a.length\le 5000$ 的话，平常的二维数组就不能使用了，要使用滚动数组。
2.因为求出来的最长公共子序列是不被计算在答案里面的（不懂的再看一遍上面），所以在计算答案的时候要减去最长公共子序列的长度。

最后，祝大家早日
请添加图片描述

上代码

#include<iostream>
#include<cstring>using namespace std;string      a,b;
int         n;
int         f[3][5010];void work(string x,string y)
{for(int i=1; i<=x.size(); i++){for(int j=1; j<=y.size(); j++){if(x[i-1]==y[j-1])f[2][j]=f[1][j-1]+1;elsef[2][j]=max(f[1][j],f[2][j-1]);}for(int j=1; j<=y.size(); j++)f[1][j]=f[2][j];}return;
}int main()
{// cout<<sizeof(f)/1024<<" KB"<<endl;cin>>a;n=a.size();b=a;for(int i=0,j=a.size()-1; i<j; i++,j--)swap(b[i],b[j]);work(a,b);cout<<n-f[1][n]<<endl;return 0;
}