蓝桥杯 3. 密码脱落

密码脱落

原题目链接
题目描述

X 星球的考古学家发现了一批古代留下来的密码。
这些密码是由 A、B、C、D 四莳植物的种子串成的序列。
细致分析发现&#xff0
c;这些密码串当初应该是前后对称的&#xff0
8;即镜像串&#xff0
9;。
由于年代久远&#xff0
c;其中许多种子脱落了&#xff0
c;因此有些串可能失去了镜像的特征。
你的任务是：

• 给定一个现在看到的密码串&#xff0
  c;
  
• 计算出至少脱落多少个种子&#xff0
  c;才能使得当初的串酿成现在的样子。
  

---

输入描述

• 输入一行&#xff0
  c;表现现在看到的密码串&#xff0
  8;字符串长度不凌驾 10
  0
  0
  &#xff0
  9;。
  

---

输出描述

• 输出一个正整数&#xff0
  c;表现至少脱落了多少个种子。
  

---

输入输出样例
示例 1
输入

1. ABCBA

复制代码

输出

1. 0

复制代码

---

示例 2
输入

1. ABDCDCBABC

复制代码

输出

1. 3

复制代码

---

&#xff0
8;阐明：脱落越少&#xff0
c;保持镜像结构越好&#xff0
c;求最少脱落的数目。&#xff0
9;
c&#43
;&#43
;代码

1. #include<bits/stdc&#43
2. ;&#43
3. ;.h>using namespace std;string a, b;int n;int main() {    cin >> a;    b = a, reverse(a.begin(), a.end());    n = a.size();    vector<int> last(n &#43
4. ; 1), now(n &#43
5. ; 1);    for (int i = 1; i <= n; i&#43
6. ;&#43
7. ;) {        for (int j = 1; j <= n; j&#43
8. ;&#43
9. ;) {            now[j] = a[i - 1] == b[j - 1] ? last[j - 1] &#43
10. ; 1 : max(last[j], now[j - 1]);        }        last = now;    }    cout << n - last[n];    return 0
11. ;}//by wqs

复制代码

算法解析

其实就是最长公共子序列问题
求出s和它的反转sr的最长公共子序列&#xff0
c;它是一个回文串
必要添加的字符个数就是长度减去这个子序列的长度
用求最长公共子序列的常规方法-动态规划来解

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123
.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。