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

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

---

原题链接

P1435
题目类型：$普及+/提高$
AC记录：Accepted

题目大意

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

输入格式

一个字符串。

输出格式

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

$\mathbf{S}\mathbf{a}\mathbf{m}\mathbf{p}\mathbf{l}\mathbf{e}$ $\mathbf{I}\mathbf{n}\mathbf{p}\mathbf{u}\mathbf{t}$

Ab3bd

$\mathbf{S}\mathbf{a}\mathbf{m}\mathbf{p}\mathbf{l}\mathbf{e}$ $\mathbf{O}\mathbf{u}\mathbf{t}\mathbf{p}\mathbf{u}\mathbf{t}$

2

$\mathbf{H}\mathbf{i}\mathbf{n}\mathbf{t}\&\mathbf{E}\mathbf{x}\mathbf{p}\mathbf{l}\mathbf{a}\mathbf{i}\mathbf{n}$
字符串变成dAb3bAd或Adb3bdA。

数据范围

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

解题思路

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

---

求最长公共子序列，无非就是把字符从两个字符串一个一个插入，然后进行动态转移。设$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{array}{ll}{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{array}$$
最后的答案就是$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;
}

完美切题$\sim$

这篇关于P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---