【动态规划】P8638 [蓝桥杯 2016 省 A] 密码脱落

题解：P8638 [蓝桥杯 2016 省 A] 密码脱落

题目传送门：P8638 密码脱落

一、题目描述

考古学家发现了一些由 A、B、C、D 四种种子组成的密码串，这些串原本是回文串（前后对称），但由于部分种子脱落，现在可能不再对称。我们需要计算最少脱落了多少个种子才能变成现在看到的样子。

二、题目分析

给定一个字符串，我们需要找到一个最接近它的回文串，使得当前字符串是该回文串的子序列（可以通过删除字符得到）。最少脱落数即为原字符串长度减去其最长回文子序列的长度。

三、问题思考

算法分析

• 回文串性质：正读反读相同，如 “ABCBA”
• 子序列：不改变字符顺序，删除任意数量字符得到的序列
• 关键转化：最少脱落数 = 字符串长度 - 最长回文子序列长度

前置知识

• 动态规划：用于高效计算最长回文子序列
• 字符串反转：回文串的反转是其本身，利用此性质可以转化为最长公共子序列问题

四、动态规划思路

a. 状态表示

定义 f[i][j] 表示原字符串前 i 个字符与反转字符串前 j 个字符的最长公共子序列长度

b. 初始化

f[0][j] = f[i][0] = 0（空字符串的公共子序列长度为0）

c. 状态转移

• 当 s1[i-1] == s2[j-1] 时：f[i][j] = f[i-1][j-1] + 1
• 否则：f[i][j] = max(f[i-1][j], f[i][j-1])

d. 最终结果

最少脱落数 = 字符串长度 n - f[n][n]

五、代码实现

#include <bits/stdc++.h>
using namespace std;string s1, s2;
int f[1010][1010]; // DP数组void solve() {cin >> s1;s2 = s1;reverse(s2.begin(), s2.end()); // 反转字符串int n = s1.size();for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (s1[i-1] == s2[j-1]) {f[i][j] = f[i-1][j-1] + 1; // 字符匹配时长度+1} else {f[i][j] = max(f[i-1][j], f[i][j-1]); // 不匹配时取较大值}}}cout << n - f[n][n]; // 输出最少脱落数
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

六、重点细节

1. 字符串索引：C++中字符串从0开始，所以比较的是s1[i-1]和s2[j-1]
2. DP数组初始化：全局数组自动初始化为0，无需手动初始化
3. 反转字符串：通过反转将回文问题转化为LCS问题
4. 最终计算：n - f[n][n]直接得到结果

七、复杂度分析

• 时间复杂度：O(n²)，双重循环遍历字符串
• 空间复杂度：O(n²)，使用二维DP数组

八、总结

本题通过将原问题转化为最长公共子序列问题，巧妙地利用动态规划求解。关键点在于：

1. 理解回文串与反转字符串的关系
2. 掌握动态规划的状态转移方程
3. 正确处理字符串索引和边界条件

这种将复杂问题转化为经典算法问题的思路，在竞赛编程中非常实用。