题解 P4302 【[SCOI2003]字符串折叠】

折叠的定义如下：

一个字符串可以看成它自身的折叠。记作S = S

X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。

如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB

给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

讲讲我的做法

题目大意：对一个字符串进行折叠是它长度最小

看一眼数据范围：哇！字符串长度不超过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个循环并成一个循环，但为了让大家看的更清楚，就不演示了