折叠的定义如下:
例如,因为 $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}$。
仅一行,即字符串 $S$,长度保证不超过 $100$。
输出一行一个整数,即最短的折叠长度。
区间 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
就挂的很惨……)