问题问的是最少可以把一个字符串分成几段,使每段都是回文串。
一开始想直接区间DP,dp[i][j]表示子串[i,j]的答案,不过字符串长度1000,100W个状态,一个状态从多个状态转移来的,转移的时候要枚举,这样时间复杂度是不可行的。
然后我就想降维度了,只能线性DP,dp[i]表示子串[0,i]的答案。这样可以从i-1转移到i,str[i]单独作一段或者str[i]能和前面的组成回文串,方程如下:
dp[i]=min(dp[i-1]+1,dp[j-1]+1) (子串[j,i]是回文串)
现在问题是怎么快速判断一个字符串的任意子串是否是回文串。
我想该不会要用字符串的一些数据结构或算法吧。。忽然又想到区间DP,这个问题是可以用区间DP解决的:
dp2[i][j]表示子串[i,j]是否是回文串
而转移只要一步即可:
dp2[i][j] = (str[i]==str[j] && dp2[i+1][j-1])
因此这就可以在O(strlen2)预处理完并在O(1)时间复杂度下判断任意区间是否是回文串。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str[];
bool palindrome[][];
int d[];
int main(){
int t;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%s",str);
int n=strlen(str); for(int i=; i<n; ++i){
for(int j=; j<n; ++j){
palindrome[i][j]=(i>=j);
}
}
for(int len=; len<=n; ++len){
for(int i=; i+len<=n; ++i){
if(str[i]==str[i+len-] && palindrome[i+][i+len-]) palindrome[i][i+len-]=;
}
} d[]=;
for(int i=; i<n; ++i){
if(palindrome[][i]){
d[i]=;
continue;
}
d[i]=d[i-]+;
for(int j=i-; j>=; --j){
if(palindrome[j][i]) d[i]=min(d[i],d[j-]+);
}
}
printf("Case %d: %d\n",cse,d[n-]);
}
return ;
}
LightOJ1044 Palindrome Partitioning(区间DP+线性DP)的更多相关文章
-
uva 11584 Partitioning by Palindromes 线性dp
// uva 11584 Partitioning by Palindromes 线性dp // // 题目意思是将一个字符串划分成尽量少的回文串 // // f[i]表示前i个字符能化成最少的回文串 ...
-
Atcoder Yet Another Palindrome Partitioning(状压dp)
Atcoder Yet Another Palindrome Partitioning 思路: 一个字符串满足条件的情况是奇数字母个数小于等于1,也就是异或起来是1<<j(0<=j& ...
-
hdu1712 线性dp
//Accepted 400 KB 109 ms //dp线性 //dp[i][j]=max(dp[i-1][k]+a[i][j-k]) //在前i门课上花j天得到的最大分数,等于max(在前i-1门 ...
-
[CodeForces - 1272D] Remove One Element 【线性dp】
[CodeForces - 1272D] Remove One Element [线性dp] 标签:题解 codeforces题解 dp 线性dp 题目描述 Time limit 2000 ms Me ...
-
1. 线性DP 300. 最长上升子序列 (LIS)
最经典单串: 300. 最长上升子序列 (LIS) https://leetcode-cn.com/problems/longest-increasing-subsequence/submission ...
-
1044 - Palindrome Partitioning(区间DP)
题目大意: 给你一个字符串,问这个字符串最少有多少个回文串. 区间DP直接搞 #include<cstdio> #include<cstring> #include&l ...
-
Lightoj 1044 - Palindrome Partitioning (DP)
题目链接: Lightoj 1044 - Palindrome Partitioning 题目描述: 给一个字符串,问至少分割多少次?分割出来的子串都是回文串. 解题思路: 先把给定串的所有子串是不 ...
-
132. Palindrome Partitioning II (String; DP)
Given a string s, partition s such that every substring of the partition is a palindrome. Return the ...
-
131. Palindrome Partitioning (Back-Track, DP)
Given a string s, partition s such that every substring of the partition is a palindrome. Return all ...
随机推荐
-
python-virtualenv(多个独立开发环境)
1. 安装virtualenv$ sudo yum install python-virtualenv 2. 创建开发环境$ virtualenv env_name 3. 启用开发环境$ cd env ...
-
【转】mysql的union、left join、 right join、 inner join和视图学习
1.联合 union 进行多个查询语句时,要求多次查询的结果列数必须一样.此时,查询的结果以第一个sql语句的列名为准且union会自动去重复我们应该使用union all. 例...... 1.联合 ...
-
HTML中noscript的用法
noscript 元素用来定义在脚本未被执行时的替代内容(文本).此标签可被用于可识别 <script> 元素用来定义在脚本未被执行时的替代内容(文本). 标签但无法支持其中的脚本的浏览器 ...
-
Bzoj 1878: [SDOI2009]HH的项链 莫队
1878: [SDOI2009]HH的项链 Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 2717 Solved: 1363[Submit][Statu ...
-
大数据与Mapreduce
第十五章 大数据与Maprudece 一.引言 实际生活中的数据量是非常庞大的,采用单机运行的方式可能需要若干天才能出结果,这显然不符合我们的预期,为了尽快的获得结果,我们将采用分布式的方式,将计算分 ...
-
S-CMS企建v3二次SQL注入
S-CMS企建v3二次SQL注入 0x01 前言 继上一篇的S-CMS漏洞再来一波!首发T00ls 0x2 目录 Sql注入二次SQL注入 0x03 Sql注入 漏洞文件:\scms\bbs\bbs. ...
-
割顶树 BZOJ1123 BLO
无向图中,求去掉点x[1,n]后每个联通块的大小. 考虑tarjan求bcc的dfs树,对于每个点u及其儿子v,若low[v]<prv[u],则v对u的父亲联通块有贡献,否则对u的子树有贡献.每 ...
-
python字典设置初始值setdefault()与get()
L = ['you','me','you','me','you','me','you'] D = {} for i in L: D[i] += 1 print(D) 执行以下代码会发生错误 Trace ...
-
深入浅析JavaScript中with语句的理解
JavaScript 有个 with 关键字, with 语句的原本用意是为逐级的对象访问提供命名空间式的速写方式. 也就是在指定的代码区域, 直接通过节点名称调用对象. with语句的作用是暂时改变 ...
-
MySQL终端下常用命令
一:控制类命令 1.show variables like "%datadir%";显示注册在variables中(一个注册表key-value的格式存储数据)key能匹配%dat ...