密码脱落

题目描述

X 星球的考古学家发现了一批古代留下来的密码。

这些密码是由 A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入描述

输入一行，表示现在看到的密码串（长度不大于 1000）。

输出描述

要求输出一个正整数，表示至少脱落了多少个种子。

输入输出样例

示例 1

输入

ABCBA```txt
>输出
```txt
0
```txt#### 示例2>输入
```txt
ABDCDCBABC

输出

3

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

总通过次数: 1860  |  总提交次数: 2184  |  通过率: 85.2%

难度: 困难   标签: 2016, 省赛, 动态规划

算法思路：动态规划求解最长回文子序列

​​问题本质​​：计算使字符串变为回文串的最少删除字符数（即原字符串长度减去最长回文子序列长度）。
​​核心思想​​：使用区间动态规划求解最长回文子序列（LPS），公式为：
最少删除数 = 字符串长度 - LPS长度

动态规划状态定义

• dp[i][j]：表示子串 s[i..j] 的最长回文子序列长度
• ​​状态转移方程​​：

算法步骤

1. ​​初始化​​：

   • 单个字符的LPS长度为1：dp[i][i] = 1
   • 相邻字符若相同则LPS为2：s[i]==s[i+1] ? dp[i][i+1]=2 : 1

2. ​​区间扩展​​（长度3到n）：

   • 枚举区间长度 len 从 3 到 n
   • 枚举左端点 i，计算右端点 j = i+len-1
   • 根据 s[i] 和 s[j] 是否相等更新 dp[i][j]

3. ​​结果计算​​：
   最少删除数 = n - dp[0][n-1]

算法演示

代码实现（C++）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 1010;
int dp[N][N];int main() {string s;cin >> s;int n = s.size();// 初始化长度为1和2的区间for (int i = 0; i < n; i++) {dp[i][i] = 1;if (i < n-1) dp[i][i+1] = (s[i] == s[i+1]) ? 2 : 1;}// 区间DP：长度从3到nfor (int len = 3; len <= n; len++) {for (int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);}}cout << n - dp[0][n-1] << endl;return 0;
}

代码解析

1. ​​初始化阶段​​（L12-L17）：

   • 对角线 dp[i][i]=1（单字符必为回文）
   • 相邻字符若相等则LPS=2，否则为1

2. ​​核心DP循环​​（L20-L27）：

   • 外层循环：区间长度 len 从3到 n
   • 内层循环：左端点 i 遍历所有起始位置
   • 根据端点字符是否相等选择转移路径

3. ​​结果输出​​（L29）：
   直接计算 n - dp[0][n-1]

实例验证

​​输入​​	​​LPS​​	​​长度​​	​​删除数​​	​​输出​​
"ABCBA"	"ABCBA"	5	5-5=0	0
"ABDCDCBABC"	"ABDCDBA"	7	10-7=3	3
"A"	"A"	1	1-1=0	0
"AB"	"A"或"B"	1	2-1=1	1

注意事项

1. ​​边界处理​​：

   • 当 j = i+1 时需单独初始化
   • 空串情况（题目保证非空）

2. ​​空间优化​​：

   • 使用滚动数组可将空间复杂度从 O(n2) 降为 O(n)

   int dp[2][N];  // 奇偶行交替计算

3. ​​时间效率​​：

   • 时间复杂度 O(n2)，n=1000 时约 106 次操作
   • 1秒内可完成最大规模数据

多方位测试点

​​测试类型​​	​​输入样例​​	​​预期输出​​	​​验证要点​​
最小边界	"A"	0	单字符处理
相邻字符	"AA"/"AB"	0/1	双字符回文判断
全相同字符	"AAAAA"	0	完整回文处理
无回文子序列	"ABCDEF"	5	最坏情况性能
交叉回文	"ABADEDBA"	2	复杂序列处理
最大长度(1000)	全A字符串	0	时间/空间边界

优化建议

1. ​​空间优化​​（滚动数组）：

   bool cur = 0;
   for (int len=2; len<=n; len++) {cur = !cur;for (int i=0; j=i+len-1 < n; i++) {if (s[i]==s[j]) dp[cur][j] = dp[!cur][j-1] + 2;else dp[cur][j] = max(dp[!cur][j], dp[cur][j-1]);}
   }

2. ​​分支优化​​：

   // 预处理字符匹配
   if (s[i]==s[j]) dp[i][j] = dp[i+1][j-1] + 2;
   else dp[i][j] = max(dp[i][j-1], dp[i+1][j]); 

3. ​​并行计算​​（OpenMP）：

   #pragma omp parallel for
   for (int len=3; len<=n; len++) {// 内层循环独立
   }