洛谷P4302 [SCOI2003]字符串折叠题解

题目链接：P4302 [SCOI2003]字符串折叠

题意：

折叠的定义如下：

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

\(X(S)\) 是 \(X(X>1)\) 个 \(S\) 连接在一起的串的折叠，记作 \(X(S) = SSSS\dots S(x \,\texttt{个}\,S)\)。

如果 \(A = A^{\prime}, B = B^{\prime}\) ，则 \(AB = A^{\prime}B^{\prime}\) 。例如，因为 \(\mathtt{3(A)} = \mathtt{AAA}, \mathtt{2(B)} = \mathtt{BB}\)，所以 \(\mathtt{3(A)C2(B)} = \mathtt{AAACBB}\) ，而 \(\mathtt{2(3(A)C)2(B)} = \mathtt{AAACAAACBB}\) 。

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

输入格式：

仅一行，即字符串 \(S\) ，长度保证不超过 \(100\) 。

输出格式：

仅一行，即最短的折叠长度。

区间dp + kmp 神仙题。

设 \(f_{i,j}\) 表示区间 \([i,j]\) 的最短折叠长度。

显然边界为 \(f_{i,i} = 1\) ，最后答案为 \(f_{1,n}\) 。

下文中使用 \(a \downarrow b+c\) 表示 \(a \leftarrow \min\{a,b+c\}\)

考虑转移。第一种，直接两个串合并 \[ f_{i,j} \downarrow \min_{i\le k < j} \{f_{i,k} + f_{k+1,j}\} \] 第二种，折叠。一个原始的想法是，按套路把两个区间合并，计算他们的贡献

但我们无法得知两个区间中的某个是否已经被折叠过了，以及它们各被折叠了几次

于是尝试直接暴力枚举折叠后的子串长度，然后转移。

记 \(d=j-i+1\) ，并且 \([i,j]\) 由 \(X\) 个长度为 \(k\) 的串拼接而成（ \(d=X\cdot k\) ），则 \[ f_{i,j} \downarrow f_{i,i+k-1} + \left\lfloor{\lg X}\right\rfloor + 3 \] 然后稍微优化一下，比如枚举 \(d\) 的因数，时间复杂度 \(O(n^3 \log n)\) （~~貌似可以水过？~~）

仔细思考可以发现，很多枚举是不必要的。

根据 border 定理，一个串有长度为 \(k\) 的周期当且仅当它有长为 \(d-k\) 的 border 。

因此我们可以预处理出每个子串的最长 border （显然跑 \(n\) 遍 \(\mathtt{kmp}\) 即可）

其实就是预处理每个子串的最小周期 \(k_0\)

然后枚举 \(k=t\cdot k_0\) 为周期，这样就可以在 \(O(\log n)\) 的时间内转移第二部分了

结果复杂度瓶颈就变成了区间dp的转移（悲

时间复杂度 \(O(n^3)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(125))

char str[N];
int n,val[N],f[N][N],g[N][N];
void down(int &x,int y) { x > y ? x = y : 0;}
void init()
{
    int x=0;
    for(; x<10; ++x) val[x] = 3;
    for(; x<100; ++x) val[x] = 4;
    for(; x<N-5; ++x) val[x] = 5;
}
void KMP(int t)
{
    int *fail = g[t]+t-1; char *s = str+t-1;
    // cout << (s+1) << '\n';
    fail[1]=0;
    for(int i=2,j=0; i<=n-t+1; i++)
    {
        while(j && s[j+1] != s[i]) j=fail[j];
        if(s[j+1] == s[i]) ++j; fail[i]=j;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (str+1); n=strlen(str+1); init();
    memset(f,0x3f,sizeof(f));
    for(int i=1; i<=n; i++) {KMP(i); f[i][i] = 1;}
    // for(int i=1; i<=n; i++)
    //     for(int j=1; j<=n; j++)
    //         cout << g[i][j] << " \n"[j==n];
    for(int len=2,L; len<=n; len++)
        for(int i=1,j=i+len-1; j<=n; i++,j++)
        {
            for(int k=i; k<j; k++)
                down(f[i][j], f[i][k]+f[k+1][j]);
            L=len-g[i][j];
            if(L <= g[i][j])
                for(int k=L; k<=len; k+=L)
                    if(len%k == 0)
                        down(f[i][j], f[i][i+k-1] + val[len/k]);
        }
    cout << f[1][n] << '\n';
    return 0;
}