题解 P4302 【[SCOI2003]字符串折叠】
讲讲我的做法
题目大意:对一个字符串进行折叠是它长度最小
看一眼数据范围:哇!字符串长度不超过100!这是一道省选题,不可能给你太宽裕的时限,所以,题目基本暗示你要用\(n^{3}\)多一些的算法复杂度。
这是一道最优化的题目,常见求最优化问题的算法比如贪心,模拟,枚举我都想不出什么好办法,唯独觉得像一道区间\(dp\)
区间\(dp\)的分析
解释状态
我们用\(f[i][j]\)表示\(i\)到\(j\)这个区间内最小的长度
首先,我们可以把\(i\)~\(j\)这个区间的字符串拆成2部分处理
就有了这段代码:
for(int l=2;l<=n;l++)
for(int i=1,j=i+l-1;j<=n;i++,j++)
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
当然我用了字符串,然后加空格,这样更加符合人脑思维
也有同学喜欢用字符数组,我也写了这样的一段代码
for(int l=2;l<=n;l++){
for(int i=0,j=i+len-1;j<n;i++,j++){
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
}
}
折叠
至于如何判断能否折叠,我呢用了一个函数——\(check\),来检查一下是否可以折叠
字符串代码:
bool check(int l,int r,int len){
for(int i=l;i<=r;i++)
if(st[i]!=st[(i-l)%len+l])return false;
return true;
}
字符数组代码
bool check(char s[],int n,int len){
for(int i=len;i<n;i++)
if(s[i]!=s[i%len])return false;
return true;
}
判断好了是否可以折叠,我们就可以去写状态了,从\(i\)~\(j\),判断区间折叠的循环节
字符串代码
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
for(int k=i;k<j;k++){
int len=k-i+1;
if(l%len!=0)continue;
if(check(i,j,len))f[i][j]=min(f[i][j],f[i][k]+2+m[l/len]);
}
}
}
字符数组代码
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<n;i++,j++){
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
for(int k=i;k<j;k++){
int len=k-i+1;
if(l%len!=0)continue;
if(check(s+i,l,len))f[i][j]=min(f[i][j],f[i][k]+2+m[l/len]);
}
}
}
边界条件以及初始化
刚刚的代码里出现里\(m\),现在我就来解释一下\(m\)数组是干什么的
\(m[i]\)的值表示的是i的位数,因为字符串的长度跟数字的位数有关
提到了\(m\)数组的左右自然由于提及如何用代码实现
我用的是最简单的方法,\(for\)循环扫,注意:100也要赋值,万一数据给你100个同样的字符
for(int i=1;i<=9;i++)m[i]=1;
for(int i=10;i<=99;i++)m[i]=2;
m[100]=3;
现在我们想一想初始化怎么做?
显然,\(f[i][i]=1\),如何数组的初值要设为\(INF\)
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)f[i][i]=1;
现在我们已经做完了所有的步骤,让我们看一看完整代码吧
字符串代码
#include <bits/stdc++.h>
using namespace std;
string st;
int n,m[110],f[110][110];
bool check(int l,int r,int len){
for(int i=l;i<=r;i++)
if(st[i]!=st[(i-l)%len+l])return false;
return true;
}
int main(){
cin>>st;
n=st.size();
st=' '+st;
for(int i=1;i<=9;i++)m[i]=1;
for(int i=10;i<=99;i++)m[i]=2;
m[100]=3;
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)f[i][i]=1;
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<=n;i++,j++){
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
for(int k=i;k<j;k++){
int len=k-i+1;
if(l%len!=0)continue;
if(check(i,j,len))f[i][j]=min(f[i][j],f[i][k]+2+m[l/len]);
}
}
}
printf("%d",f[1][n]);
return 0;
}
字符数组代码
#include <bits/stdc++.h>
using namespace std;
char s[110];
int n,m[110],f[110][110];
bool check(char s[],int n,int len){
for(int i=len;i<n;i++)
if(s[i]!=s[i%len])return false;
return true;
}
int main(){
scanf("%s",s);
n=strlen(s);
for(int i=1;i<=9;i++)m[i]=1;
for(int i=10;i<=99;i++)m[i]=2;
m[100]=3;
memset(f,0x3f,sizeof(f));
for(int i=0;i<n;i++)f[i][i]=1;
for(int l=2;l<=n;l++){
for(int i=1,j=i+l-1;j<n;i++,j++){
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
for(int k=i;k<j;k++){
int len=k-i+1;
if(l%len!=0)continue;
if(check(s+i,l,len))f[i][j]=min(f[i][j],f[i][k]+2+m[l/len]);
}
}
}
printf("%d",f[0][n-1]);
return 0;
}
时间复杂度
看上去我们连续套了4个循环,然而真的时间复杂度就达到了\(n^{4}\)吗?其实不是的
首先\(n^{3}\)是肯定要的,那么为什么时间复杂度没有达到\(n^{4}\)呢!
原因在于我们的continue剪枝,它能够给这个\(n^{4}\)的复杂度加上一个\(log\)
为什么?
我们要check的显然是\(l\)的因数,然而\(l\)的因数个数\(\approx\) \(\log{l}\)
现实当中的复杂度还会更小,因为\(check\)的复杂度没有到\(O(n)\),它不是从头开始,没有到头结束,并且一旦发现错误后会直接\(return\)
其实可以把里面的2个循环并成一个循环,但为了让大家看的更清楚,就不演示了
最新文章
- CSS的未来
- iOS学习笔记——滚动视图(scrollView)
- Duilib源码分析(六)整体流程
- Traditional Language Model
- [Web开发] 在HTML代码里面如何判断IE版本
- (2016 年) githup 博客地址 : https://github.com/JMWY/MyBlog
- iOS 随记
- 安装repcached,并且测试其双向复制是否成功
- c#开发Mongo笔记第二篇
- C#使用oledb方式将excel数据导入到datagridview后数据被截断为 255 个字符
- js获取元素transform参数得出的个人理解
- 转:Hprose for php(三)——客户端
- hand第四次考核
- BigData-‘基于代价优化’究竟是怎么一回事?
- 解决Warning: unlink(/storage/cache/cache.catalog.language.1556158719): No such file or directory in /system/library/cache/file.php on line 68问题
- C/C++字符串使用整理
- cocos creator热更新教程
- windows下安装Git安装
- Haskell语言学习笔记(76)Data.Tree
- Spring Boot 报错:Error creating bean with name &#39;entityManagerFactory&#39; defined in class path resource