题目描述

难度分:$2400$

输入长度$\leq 8000$的字符串$s$，只包含小写英文字母。

你需要压缩$s=s1 \times c1 + s2 \times c2 + …$

例如$abababcc = ab \times 3 + c \times 2$。

压缩后的长度定义为$|s1| + |c1| + |s2| + |c2| + …$

其中$|c1|$表示整数$c1$的十进制长度。例如$ab \times 3 + c \times 2$的长度为$2 + 1 + 1 + 1 = 5$。

输出$s$压缩后的最短长度。

输入样例$1$

aaaaaaaaaa

输出样例$1$

3

输入样例$2$

abcab

输出样例$2$

6

输入样例$3$

cczabababab

输出样例$3$

7

算法

划分型DP+$KMP$算法

首先可以发现一个比较显然的性质，对于任意一段子串$[l,r]$，把它压缩成若干个最小周期是最划算的（数字长度的增加是很慢的，多举几个例子就能发现这一点）。

状态定义

$dp[i]$表示前缀$[1,i]$压缩之后的最短长度，在这个定义下答案就是$dp[n]$。

状态转移

枚举最后一段$[j,i]$（$j \leq i$），状态转移方程即为$dp[i]=dp[j-1]+cost(j,i)$，其中$cost(j,i)$是子串$[j,i]$压缩之后的最短长度。因此我们只需要求出子串$[j,i]$的最短周期$T$就可以了，这时候能将$[j,i]$表示为$cnt=\frac{i-j+1}{T}$个$T$连接而成，$cost(j,i)=|T|+bits(cnt)$，其中$bits(x)$表示数字$x$的数位数，$|T|$表示字符串$T$的长度。枚举左端点$l \in [1,n]$，对于固定的左端点$l$，利用$KMP$算法遍历右端点$r \in [l,n]$计算子串$[l,r]$的最小周期$T$，然后进行状态转移$dp[r]=min_{l \leq r}(dp[l-1]+|T|+bits(\frac{r-l+1}{T}))$。

复杂度分析

时间复杂度

状态数量是$O(n)$，单次转移的时间复杂度为$O(n)$，所以整个算法的时间复杂度为$O(n^2)$。

空间复杂度

除了输入的字符串$s$，DP的状态数组$dp$空间复杂度为$O(n)$；$[1,8000]$每个数的数位存在$bits$数组中，空间复杂度为$O(n)$；$KMP$时需要用到的$fail$数组（或者$next$数组），空间复杂度为$O(n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 8010, INF = 0x3f3f3f3f;
int n, dp[N], fail[N], bits[N];
char s[N];

int get_bits(int x) {
    int ans = 0;
    while(x > 0) {
        ans++;
        x /= 10;
    }
    return ans;
}

void init(int n) {
    for(int i = 0; i <= n; i++) {
        dp[i] = INF;
        bits[i] = get_bits(i);
    }
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    init(n);
    dp[0] = 0;
    for(int l = 1; l <= n; l++) {
        fail[l] = 0;
        for(int r = l + 1; r <= n; r++){
            fail[r] = 0;
            int k = fail[r - 1];
            while(1) {
                if(s[r] == s[l + k]){
                    fail[r] = k + 1;
                    break;
                }
                if(k == 0) break;
                k = fail[l + k - 1];
            }
        }
        for(int r = l; r <= n; r++) {
            // 把子串[l,r]压缩
            int len = r - l + 1;
            int f = fail[r];
            int cnt = 1;
            if(len % (len - f) == 0) {
                cnt = len / (len - f);
            }
            int T = len / cnt;
            dp[r] = min(dp[r], dp[l - 1] + bits[cnt] + T);
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}