AcWing 1222. 密码脱落
2024-09-01 09:18:36
题目描述:
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。
由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。
你的任务是:
给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。
题目大意:给定一个串,求至少增加其中几个字符,才可使其成为回文串。
等价于:给定一个串,求至少删除其中几个字符,才可使其成为回文串。
而删除的数量=串的长度-最大回文串长度。
于是该题为求一个串的最大回文串长度。
解决方法:DP
集合:所有S[L,R]之间的回文子序列的集合
集合划分:
#include <cstdio>
#include <string.h>
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;
}
最新文章
- ubuntu 报错: The system is running in low-graphics mode
- web.config设置和取值
- Extjs的学习及MIS系统实践应用(系列文章)
- Nibbler – 免费的网站测试和指标评分工具
- OC-点语法
- As 和 Is的区别
- (转)Java并发编程:volatile关键字解析
- Redis学习手册(持久化)
- Windows server 2008 r2 开启Aero
- 异步任务利器Celery(一)介绍
- win10更改无线网卡的MAC地址
- Oracle事务与锁 知识点摘记
- ntp---时钟同步服务
- jq、js判断元素是否在可视区域内
- 《Java并发编程的艺术》并发编程的挑战(一)
- Gym - 100989E
- Caffe源码中math_functions文件分析
- request笔记记录
- 剑指offer 09变态跳台阶
- angularJS1笔记-(9)-自定义指令(restrict/template/replace)