P4302 字符串折叠

字符串折叠：拼接与周期压缩

问题

P4302 字符串折叠 - 洛谷
将字符串写成尽可能短的折叠形式。连续重复的子串可以表示为 k(S)，括号中的 S 仍然可以继续折叠。

这又是一个连续区间问题（子串），所以自然考虑区间DP 的形式。

对于某一段子串 $S[l, r]$，它最后的结构只有两种：由左右两段直接拼接形成，或者是由某个较短的循环节重复得到的。

因此定义：$f[l][r]$ 表示子串 $S[l\dots r]$ 的最短表示长度。

接着考虑这两种情况是怎么转移过来的：

1. 拼接，枚举最后一次分割的位置 $k$：

$$f[l][r]=\min_{l\le k<r}\{f[l][k]+f[k+1][r]\}$$

2. 循环压缩，设区间长度为 $len = r - l + 1$，如果 $p\mid len$，并且 $s[l\dots r]$ 的循环节长度为 $p$，那么整段可以写成：

$$\frac{len}{p}\bigl(s[l\dots l+p-1]\bigr).$$

循环节本身也可能继续压缩，所以代价不是裸长度 $p$，而是：$f[l][l+p-1]+\operatorname{digits}(len/p)+2$

其中 $2$ 是一对括号的长度。

▶

P4302

string s;
ll f[maxn][maxn];

int calc( int x ) {
    int res = 0;
    while( x ) {
        res ++;
        x /= 10;
    }
    return res;
}

bool check( int l, int r, int p ) {
    for( int i = l + p; i <= r; i ++ ) {
        if( s[i] != s[i-p] ) return 0;
    }
    return 1;
}

void solve( ) {
    cin >> s;
    int n = s.length( );
    s = " " + s;

    for( int i = 1; i <= n; ++ i ) f[i][i] = 1;
    
    for( int len = 2; len <= n; ++ len ) {
        for( int l = 1; l + len - 1 <= n; ++ l ) {
            int r = l + len - 1;
            f[l][r] = len;

            for( int k = l; k < r; ++ k ) {
                f[l][r] = min( f[l][r], f[l][k] + f[k+1][r] );

                for( int p = 1; p < len; ++ p ) {
                    if( len % p != 0 ) continue;
                    if( check( l, r, p ) ) {
                        int cnt = calc( len / p );
                        f[l][r] = min( f[l][r], f[l][l + p - 1] + cnt + 2 );
                    }
                }
            }
        }
    }
    cout << f[1][n] << '\n';
}

区间按长度递增枚举，保证转移依赖的短区间已经求出。判断周期时，可以逐位检查 $s[i]=s[i-p]$。

记录

这题保留为 C 类记录。它提供了一个较完整的区间 DP 建模样例：先问“一个区间的最终结构有哪些可能”，再分别为拼接结构和整体重复结构设计转移。