Codeforces 825F - String Compression

825F - String Compression

题意

给出一个字符串，你要把它尽量压缩成一个短的字符串，比如一个字符串ababab你可以转化成3ab，长度为 3，比如bbbacacb转化成3b2ac1b，长度为 7，aaaaaaaaaa转化为10a，长度为 3。

分析

求转换后的最短字符串，那么怎么去组合字符串中的子串是关键。

考虑 dp，dp[1...L] 对应字符串 S[0...L-1] 。dp[i] 表示字符串 S[0, i - 1] 转化后的字符串长度，dp[0] = 0。

状态转移方程：$ dp[i] = min(dp[i], dp[j] + has[j][i - 1]) $，其中 $has[j][i - 1]$ 表示字符串 S[j, i - 1] 由某个字符（串）重复 k 次，k 取最大的时候，转化后的长度。比如abab，ab重复了两次，那么 $has$ 的值为 3。

那么我们就要去预处理 has 的值，一个字符串（长度为 L）由 k 个连续且相同的子串组成，求 k 的最大值。这个问题不就是某个经典的字符串题吗？戳

当然不用后缀数组那么麻烦，那只是为了练习 : ) 。

考虑 KMP 算法中 nxt 数组的含义，对于字符串abcabc，那么 $nxt[6] = 3$，即前缀后缀相同的子串长，我们称最小连续的那个子串为循环节，设 $l = L - nxt[L]$，如果 $l$ 刚好整除 $L$，那么 $l$ 就是循环节的长度。对于字符串ababab， $nxt[6]=4$ ，假如后面还有字符，第 7 个字符导致失配，最后的四个字符abab不用再去匹配了，直接由abab向后匹配，正好是右移了一个循环节的位置。

code

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 8000 + 10;

const int INF = 1e9;

char T[MAXN];

int nxt[MAXN];

void getNext() {

    int tlen = strlen(T);

    int j, k;

    j = 0;

    k = -1;

    nxt[0] = -1;

    while(j < tlen)

        if(k == -1 || T[j] == T[k])

            nxt[++j] = ++k;

        else

            k = nxt[k];

}

int getl(int x) {

    int cnt = 0;

    while(x) {

        cnt++;

        x /= 10;

    }

    return cnt;

}

char S[MAXN];

int dp[MAXN];

int has[MAXN][MAXN];

int main() {

    scanf("%s", S);

    int L = strlen(S);

    for(int i = 0; i < L; i++) {

        has[i][i] = 2;

        int l = 0;

        for(int j = i; j < L; j++) {

            T[l++] = S[j];

        }

        T[l] = 0;

        getNext();

        l = 0;

        for(int j = i + 1; j < L; j++) {

            l++;

            int k = j - i + 1;

            int p = k - nxt[l + 1];

            if(k % p == 0) {

                has[i][j] = getl(k / p) + p;

            } else has[i][j] = j - i + 2;

        }

    }

    dp[0] = 0; // dp[1..L] 对应字符串 S[0..L-1]

    for(int i = 1; i <= L; i++) {

        dp[i] = i + 1;

        for(int j = 0; j < i; j++) {

            // [j + 1, i] 对应字符串的 [j, i - 1]

            dp[i] = min(dp[i], dp[j] + has[j][i - 1]);

        }

    }

    printf("%d\n", dp[L]);

    return 0;

}

巴特西

Codeforces 825F - String Compression

825F - String Compression

题意

分析

code

最新文章

热门文章