AcWing|AcWing 1222. 密码脱落
题目链接
题目描述：
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
【AcWing|AcWing 1222. 密码脱落】题目大意：给定一个串，求至少增加其中几个字符，才可使其成为回文串。
等价于：给定一个串，求至少删除其中几个字符，才可使其成为回文串。
而删除的数量=串的长度-最大回文串长度。
于是该题为求一个串的最大回文串长度。
解决方法：DP
集合：所有S[L，R]之间的回文子序列的集合
集合划分：
文章图片
#include
#include const int N = 1010;
char s[N];
int f[N][N];
int main()
{
scanf("%s", s);
int n = strlen(s);
for (int len = 1;
len <= n;
len ++ )//区间DP枚举长度（因为常规方法第一维要用l+1更新l对应的值）
for (int l = 0;
l + len - 1 < n;
l ++ )
{
int r = l + len - 1;
if (len == 1) f[l][r] = 1;
else
{
if (s[l] == s[r]) f[l][r] = f[l + 1][r - 1] + 2;
if (f[l][r - 1] > f[l][r]) f[l][r] = f[l][r - 1];
if (f[l + 1][r] > f[l][r]) f[l][r] = f[l + 1][r];
}
}printf("%d\n", n - f[0][n - 1]);
return 0;
}
推荐阅读
- AcWing|AcWing 1047. 糖果
- AcWing|AcWing 1050. 鸣人的影分身
- linux|CentOS7忘记MySQL密码后重置
- 人工智能|艾伦·图灵破译纳粹密码，被视为计算机和人工智能领域的先驱。
- 存储用户密码应该使用什么加密算法（）
- 算法|Acwing1230. K倍区间
- acwing|【acwing】846. 树的重心**
- Vue|Vue 两个字段联合校验之修改密码功能的实现
- Kali系统sslscan工具安装、修改root密码及ssh服务开启
- 拜托，不用记密码真的超酷好吗（）