题解 P4302 【[SCOI2003]字符串折叠】
kradcigam
2019-08-28 11:33:24
- Update 2020-6-5：感谢 @[blanc_x](https://www.luogu.com.cn/user/101620) 帮忙检查出了一处笔误。
- Update 2020-8-7：感谢 @[Garrison](https://www.luogu.com.cn/user/154334) 指出错误。
- Update 2021-8-12：修改优化了排版&解答评论问题：
- 关于 4 重循环：包含函数里的一重，请不要再问这样的问题了。
- Update 2021-10-16：感谢 @[0Arctic0](https://www.luogu.com.cn/user/367991) 帮助修改了时间复杂度部分，增强语言的严谨性。
---
## 讲讲我的做法
题目大意：对一个字符串进行折叠是它长度最小。
看一眼数据范围：哇！字符串长度不超过 **100**！这是一道省选题，不可能给你太宽裕的时限，所以，题目基本暗示你要用 $n^{3}$ 多一些的算法复杂度。
这是一道最优化的题目，常见求最优化问题的算法比如贪心，模拟，枚举我都想不出什么好办法，唯独觉得像一道区间 dp。
### 区间 dp 的分析
#### 解释状态
我们用 $f_{i,j}$ 表示 $i\sim j$ 这个区间内最小的长度。
首先，我们可以把 $i\sim j$ 这个区间的字符串拆成 2 部分处理。
就有了这段代码：
```cpp
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]);
```
当然我用了字符串，然后加空格，这样更加符合人脑思维。
也有同学喜欢用字符数组，我也写了这样的一段代码：
```cpp
for(int l=2;l<=n;l++){
for(int i=0,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]);
}
}
```
#### 折叠
至于如何判断能否折叠，我呢用了一个函数——`check`，来检查一下是否可以折叠。
字符串代码：
```cpp
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;
}
```
字符数组代码：
```cpp
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\sim j$，判断区间折叠的循环节。
字符串代码：
```cpp
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]);
}
}
}
```
字符数组代码：
```cpp
for(int l=2;l<=n;l++){
for(int i=0,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$ 的位数**，因为字符串的长度跟数字的位数有关。
我用的是最简单的方法，`for` 循环扫，**注意**：**100 也要赋值，万一数据给你 100 个同样的字符**。
```cpp
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$，其他初值设为 $∞$。
```cpp
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)f[i][i]=1;
```
现在我们已经做完了所有的步骤，让我们看一看完整代码吧。
字符串代码：
```cpp
#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;
}
```
字符数组代码：
```cpp
#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=0,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`，它的复杂度是 $\log n$。
为什么？
我们进行 `check` 操作的显然是 $l$ 的因数，而 $l$ 的因数个数$<\log{l}$。
现实当中的常数还会更小，因为 `check` 的常数很小，它不是从 $1$ 开始，也没有到 $n$ 结束，并且一旦发现错误后会直接 `return`。
其实可以把里面的 2 个循环并成一个循环，但为了让大家看的更清楚，就不演示了。