例如，因为 $3(\texttt A) \to \texttt {AAA}, 2(\texttt B) \to \texttt {BB}$，所以 $3(\texttt A) \texttt C 2(\texttt B) \to \texttt {AAACBB}$，而 $2(3(\texttt A) \texttt C) 2(\texttt B) \to \texttt {AAACAAACBB}$。

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

输入格式

输出格式

题解

区间 DP，记 $f_{i, j}$ 表示子串 $s[i..j]$ 的最短的折叠长度，则 $f_{i, i} = 1$，所求即 $f_{1, n}$。

考虑转移，首先是第 3 种定义，转移比较简单：$$ f_{i, j} \downarrow \min_{i \leq k < j} \{ f_{i, k} + f_{k+1, j} \} $$

接下来就是第 2 种定义的转移，当然，子串 $s[i..j]$ 要满足第 2 种定义的条件。如果子串 $s[i..j]$ 由 $X$ 个长度为 $k$ 的相同的串构成 ($X > 1$)，则有 $$ f_{i, j} \downarrow f_{i, i+k-1} + \left \lfloor \lg X \right \rfloor + 3 $$ (注意数字也是占长度的)

关键就是如何找出匹配的 $X$ 和 $k$。令 $d = j-i+1$ 为该子串的长度，则 $d = X \cdot k$，因此 $k \leq \left \lfloor \dfrac d2 \right \rfloor$，且这个长度为 $k$ 的串是它的一个周期。

由 border 定理，一个串有一个长度为 $k$ 的周期 ⇔ 它有一个长度为 $d - k$ 的 border。于是，我们可以跑 $n$ 遍 KMP 算法 (或暴力 Hash) 预处理出每个子串的最长 border，即最小周期 $k_0$。

那么，它的每个长度 $\leq \left \lfloor \dfrac d2 \right \rfloor$ 的周期都是 $k_0$ 的倍数。枚举 $k_0$ 的倍数，即得它的周期。由于它需要完整的 $X$ 个串，故还需要 $k \mid d$，然后更新即可。

时间复杂度 $O(n^3)$，注意代码中的 $f_{i, j}$ 表示的是开区间，和上面不同。

代码

#include <bits/stdc++.h>
#define N 136
using namespace std;

char str[N], cost[N];
int n, d, i, j, k;
int cyc;
int f[N][N], border[N][N];

void down(int &x, const int y) {x > y ? x = y : 0;}

void KMP(int beg){
    int i, j = 0, *f = border[beg] + beg; char *s = str + (beg - 1);
    f[0] = -1; f[1] = 0;
    for(i = 1; i <= n - beg; f[++i] = ++j)
        for(; j >= 0 && s[j] != s[i]; j = f[j]);
}

int main(){
    scanf("%s", str); n = strlen(str);
    memset(f, 63, sizeof f);
    for(i = 0; i < 10; ++i) cost[i] = 3;
    for(; i < 100; ++i) cost[i] = 4;
    for(; i < N; ++i) cost[i] = 5;
    for(i = 1; i <= n; ++i) {KMP(i); f[i][i + 1] = 1;}
    for(d = 2; d <= n; ++d)
        for(i = 1; i <= n - d + 1; ++i){
            j = i + d;
            for(k = i + 1; k < j; ++k)
                down(f[i][j], f[i][k] + f[k][j]);
            if((cyc = d - border[i][j]) <= border[i][j])
                for(k = cyc; k < d; k += cyc)
                    if(!(d % k))
                        down(f[i][j], f[i][i + k] + cost[d / k]);
        }
    printf("%d\n", f[1][n + 1]);
    return 0;
}

坑

坑1：注意枚举周期的时候是 $k_0$ 的倍数 (k += cyc) 且 $k \mid d$ ~~(当时写成了 ++k 就挂的很惨……)~~

题目描述

输入格式

输出格式

题解

代码

坑