AcWing 1222.密码脱落

news/发布时间2024/5/24 5:43:40

[题目概述]

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入格式

共一行，包含一个由大写字母ABCD构成的字符串，表示现在看到的密码串。

输出格式

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

数据范围

输入字符串长度不超过1000

输入样例1：

ABCBA

输出样例1：

输入样例2：

ABDCDCBABC

输出样例2：

输入给出的是减少字母后的字符串，需要我们求原来的字符串至少少了几个字母才变成现在的串，也就是让我们求最少添加几个字母能变成原来的镜像串，也就是回文串
回文串的特征就是左右对称，那每个字母都是成对出现的，现在不是回文串肯定就有字母是单个的，因此我们可以将单个的字母删除，剩下的字符还是回文串。
举个例子（样例2）

ABDCDCBABC
删除这三个字母后变成了
ABCDCBA就是一个回文串了，并且最少得删除这三个，因此输出的答案就是3

那么现在我们就是要求该串中的最长回文序列的长度，再用总长度减去它就是答案。
注意：此处是回文序列，不是回文串，可以不连续。

状态表示：f[l][r]
*****集合：s[l,r]之间的回文子序列的长度
*****属性：最大值
状态计算：按回文子序列是否包含左右端点分
******l,r都包含：f[l + 1][r - 1] + 2
******含l不含r：f[l][r - 1]（这个表达式表示的是一定不含r但含不含l不确定，他是包含我们这种含 l 不含r的情况，因为是求最大值，他所求出来的最大值肯定是包含我们这种情况的）
******含r不含l：f[l + 1][r]
******都不含：f[l + 1][r - 1]

我们可以合并成三种情况，最后一种情况肯定是比第一种情况小的。

完整代码

有一个特殊的点，因为我们需要用到l + 1, r - 1这种，一定不能按顺序从大到小进行枚举。
有一种区间问题的通用办法就是先枚举区间长度，再枚举左端点，用二者求出右端点。
这样的话我们的更新一定都是在len的范围内，不会发生我们需要用但是还没求的情况。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1010;
char s[N];
int f[N][N];
int main (){cin >> s;int n = strlen(s);for(int len = 1; len <= n; len ++){for(int l = 0; l + len - 1 < n; l ++){int r = l + len - 1;// 长度为1，是回文子序列，赋值为1if(len == 1) f[l][r] = 1;else{if(s[l] == s[r]) f[l][r] = f[l + 1][r - 1] + 2;else f[l][r] = max(f[l][r],max(f[l + 1][r], f[l][r - 1]));}}}cout << n - f[0][n - 1] << endl;return 0;
}