洛谷P1435 回文字串(dp)
2024-08-28 21:32:30
题意
回文词是一种对称的字符串。任意给定一个字符串,通过插入若干字符,都可以变成回文词。此题的任务是,求出将给定字符串变成回文词所需要插入的最少字符数。
比如 “Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”,但是插入少于2个的字符无法变成回文词。
注:此问题区分大小写
Sol
自己DP太垃圾啦,于是滚来刷水题啦qwq
感觉我的做法太麻烦了。
首先不难看出,这题跟LCS有关,而且是魔改版的LCS,具体来说,我们要求的是前缀$1 - i$的反串和后缀$i - n$的LCS。
统计答案的时候分情况讨论一下
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
// #define int long long
using namespace std;
const int MAXN = * 1e6 + , INF = 1e9 + , mod = ;
inline int read() {
char c = getchar(); int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * f;
}
int f[][], N;//f[i][j]:前缀1-i,后缀j-n的最长公共子序列
char s[MAXN];
main() {
scanf("%s", s + );
N = strlen(s + );
for(int i = ; i <= N; i++) {
for(int j = N; j >= i + ; j--) {
f[i][j] = max(f[i - ][j], f[i][j + ]);
if(s[i] == s[j]) f[i][j] = max(f[i][j], f[i - ][j + ] + );
//printf("%d %d %d\n", i, j, f[i][j]);
}
}
int ans = INF;
for(int i = ; i <= N; i++)
ans = min(ans, N - - f[i - ][i + ] * ); for(int i = ; i <= N - ; i++) {
ans = min(ans, N - - (f[i - ][i + ] * ) + (s[i] != s[i + ]));
} printf("%d", ans);
return ;
}
/*
abbbbba
-- abab abbab abcdba
*/
最新文章
- Sublime Text 3 快捷键精华版
- Java优化
- HTTP请求报文和HTTP响应报文
- matlab生成HEX文件-任意信号 大于64K长度
- MySQL之不能保存表格问题
- 济南学习 Day 3 T1 pm
- linux使用:vi编辑器
- IP访问SQL数据库设置
- Java Nio 多线程网络下载
- easyui源码翻译1.32--Dialog(对话框窗口)
- Centos学习
- 关于jdbc注冊驱动的那点事
- riot.js教程【四】Mixins、HTML内嵌表达式
- CentOS在线安装Mysql5.7
- MacOS软件默认安装路径
- IIS安装以及发布
- [ZJOI2011]营救皮卡丘
- ITextSharp构造PDF文件
- LeetCode 203. Remove Linked List Elements 移除链表元素 C++/Java
- 微信小程序获取复选框全选,反选选中的值
热门文章
- 主库报 Error 12154 received logging on to the standby PING[ARC2]
- DSP编程
- c# winform DataGridView 单元格的屏幕位置
- JAVA正则表达式之 Pattern介绍
- C++ STL vector使用总结
- Codeforces Round #459 (Div. 2)The Monster[匹配问题]
- Widows下Faster R-CNN的MATALB配置(CPU)
- Unity3D 自动添加Fbx Animation Event
- ShellExecute
- 51nod1112(xjb)