P8638 [蓝桥杯 2016 省 A] 密码脱落
题目描述
X 星球的考古学家发现了一批古代留下来的密码。
这些密码是由 A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的回文串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入格式
输入一行，表示现在看到的密码串。（长度不大于 ）
输出格式
要求输出一个正整数，表示至少脱落了多少个种子。
输入输出样例 #1
输入 #1
ABCBA
输出 #1
0
输入输出样例 #2
输入 #2
ABDCDCBABC
输出 #2
3
说明/提示
蓝桥杯 2016 年省赛 A 组 I 题。
解析
怎样拆解题目？可以将题目转换成给定一个字符串，你最少需要往里面插入/补充多少个字符才能让它重新变成回文串
对于现在的密码串，里面没有脱落的那些字符，它们在原本的密码里，一定也构成了一个回文串。
为了让“脱落的字符”尽可能少，我们就必须让“没有脱落的字符”尽可能多！
所以，问题就转化成了：在当前这个字符串中，找出最长的一个“回文子序列”。（注意：子序列可以是不连续的，这就完美对应了中间有字符脱落的情况）。
所以最终就是转化成最少脱落的种子数 = 当前字符串的总长度 - 最长回文子序列的长度
接下来就是无脑套模板：找最长公共子序列
一个字符串 的“最长回文子序列”长度，等于 与 的反转字符串 之间的“最长公共子序列（LCS）”长度
- 步骤 1：拿到原字符串 。
- 步骤 2：把 倒过来，得到反转字符串 。
- 步骤 3：求 和 的最长公共子序列长度
LCS_len。 - 步骤 4：输出答案
S的总长度 - LCS_len。
状态转移方程：
设 dp[i][j] 表示字符串 的前 个字符和字符串 的前 个字符的最长公共子序列长度。
- 如果
S[i-1] == R[j-1]，说明这两个字符可以配对：dp[i][j] = dp[i-1][j-1] + 1 - 如果
S[i-1] != R[j-1]，说明它们不能同时出现在公共序列中，我们取之前的最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
代码
//
// Created by 23264 on 2026/3/10.
//
#include<bits/stdc++.h>
using namespace std;
string s;
vector<vector<int>> dp;
int len;
void solve()
{
string r = s;
reverse(r.begin(),r.end());
for (int i = 1;i <= len;i++)
{
for (int j = 1;j <= len;j++)
{
if (s[i - 1] == r[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else
{
dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
}
}
}
cout << len - dp[len][len];
}
int main()
{
cin >> s;
len = static_cast<int>(s.size());
dp.resize(len + 1,vector<int>(len + 1,0));
solve();
}