BZOJ 1068 压缩 解题报告

1068: [SCOI2007]压缩

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

　　给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。 bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程

已经解压的部分	解压结果	缓冲串
b	b	b
bM	b
bMc	bc	c
bMcd	bcd	cd
bMcdR	bcdcd	cdcd
bMcdRR	bcdcdcdcd	cdcdcdcd

　　另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

Input

　　输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

Output

　　输出仅一行，即压缩后字符串的最短长度。

Sample Input

bcdcdcdcdxcdcdcdcd

Sample Output

12

HINT

100%的数据满足：1<=n<=50

Solution

设原始文本为T。
       观察本题中的压缩算法后不难发现：压缩后的文本被“M”分割成若干个彼此独立的片段，这些片段的在解压过程中是不会相互干扰的。于是我们想到区间动态规划。

       说到区间动态规划，最自然的想法一定是设dp[i][j]表示T[i..j]压缩后的最小长度。合并状态dp[i][k]和dp[k+1][j]时，如果T[i..k]=T[k+1..j]，合并后的状态dp[i][j]=dp[i][k]+1，也就是在T[i..k]压缩后的文本后添加一个“R”;否则dp[i][j]=dp[i][k]+dp[k+1][j]+1，也就是在T[i..k]和T[k+1..j]压缩后的文本之间添加一个“M”。写出的转移过程应该类似于这样：

int main()

{

    cin >> T;

    memset(dp, 0x3F, sizeof(dp));

    len = T.length();

    for (int i = 0; i<len; i++)

    {

        dp[i][i] = 1;

    }

    for (int L = 2; L <= len; L++)

    {

        for (int i = 0; i <= len - L; i++)

        {

            int j = i + L - 1;

            dp[i][j] = L;

            for (int k = i; k < j; k++)

            {

                if (T.substr(i, k - i + 1) == T.substr(k + 1, j - k))dp[i][j] = min(dp[i][j], dp[i][k] + 1);

                else dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + 1);

            }

        }

    }

    cout << dp[0][len-1] << endl;

    return 0;

}

       结果样例输出了13，简单测试后发现，“ababababx”输出了6，于是找出问题：压缩后的文本的字符“x”前多了一个“M”。为了解决这个问题，笔者最先想到的方法是判断合并时dp[k+1][j]是否是原始长度（j-k），如果是就不加1，即：else dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + (dp[k + 1][j] == j - k ? 0 : 1)); 如此修改确实可以过样例。如果你话十分钟时间写了一个这样的程序，那恭喜，你在当年的省选可以得70分。

       以上程序的问题并不明显，我们来看一看这个数据“ababababcdcdcdcdababababcdcdcdcd”，答案是13，但以上程序的输出是10，竟然比答案“更优”。原因出在dp[0][15]和dp[16][31]的合并上，两个状态对于的字符串均为“ababababcdcdcdcd”，dp[0][15]=9，于是合并之后得到了10。但事实上，为了使“ababababcdcdcdcd”压缩后的长度为9，缓冲串已经清空过一次（处理完“abababab”后），直接添加一个“R”并不能重复整个字符串。

       假如在转移时已知最后一次清空缓冲串的位置，问题不就迎刃而解了吗？

       于是设dp[i][j][k]表示T[i..j]在满足最后一次清空缓冲串的位置为k的条件下，压缩后的最短长度。为了方便，我们认为在处理一个字符串前，缓冲串必须被清空一次，也就是单个字符“x”被压缩后会得到“Mx”，这纯粹是为了方便合并。转移方程基本上没有变，但遍历的过程及其繁琐：

for (int i = 0; i<len; i++)

{

    dp[i][i][i] = 2;

}

for (int L = 2; L <= len; L++)

{

    for (int i = 0; i <= len - L; i++)

    {

        int j = i + L - 1;

        dp[i][j][i] = L + 1;

        //当前区间、第二个区间最后一次断开的位置

        for (int k = i + 1; k <= j; k++)

        {

            //第一个区间的最后一次断开位置

            for (int cut1 = i; cut1 <= k; cut1++)

            {

                //第二个区间没有被分割

                dp[i][j][cut1] = min(dp[i][j][cut1], dp[i][k][cut1]+j-k);

                //第一、二个区间的分割位置

                for (int cutm = cut1; cutm <= min(k, j - 1); cutm++)

                {

                   dp[i][j][k] = min(dp[i][j][k], dp[i][cutm][cut1] + dp[cutm+1][j][k]);

                    if (T.substr(cut1,cutm-cut1+1) == T.substr(cutm+1,j-cutm)) dp[i][j][cut1] = min(dp[i][j][cut1], dp[i][cutm][cut1] + 1);

                }

            }

        }

    }

}

这样写正确性可以保证，但时间复杂度高达$O(n^6)$，虽然常数大约是$\frac1{32}$，可本题有10个测试点，1000ms似乎无法通过。一个可行的优化是采用预处理后只需要常数时间即可完成的字符串比较，这选用拓展Rabin-Karp，实现如下：

unsigned long long sum[51];

unsigned long long expr[51];

void init()

{

    expr[0] = 1;

    for (int i = 1; i <= len; i++)expr[i] = expr[i - 1] * seed;

    sum[len] = 0;

    for (int i = len - 1; i >= 0; i--)sum[i] = sum[i + 1] * seed + T[i];

}

inline unsigned long long sub(int l, int r)

{

    return sum[l] - sum[r + 1] * expr[r - l + 1];

}

最终的时间复杂度是$O(n^5)$，常数约为$\frac1{16}$，在本机不开O2优化运行时间444ms，在bzoj的土豆上开O2优化运行时间364ms。本机似乎大部分时间都花在启动程序上了，似乎测评机会对每个测试点减去程序的平均启动时间（可能为15ms）。

Code

#include <iostream>

#include <stdio.h>

#include <string>

#include <string.h>

#include <algorithm>

using namespace std;

const int INF = 0x3F3F3F3F;

unsigned long long seed = 33;

string T;

int len;

//dp[i][j][k]:T[i..j]且最后一次断开（加入M）的位置是k的前方，压缩后的最小长度

//若k=i，则表示没有断开，但认为前方仍然有一个M

//i<=k<=j

int dp[51][51][51];

unsigned long long sum[51];

unsigned long long expr[51];

void init()

{

    expr[0] = 1;

    for (int i = 1; i <= len; i++)expr[i] = expr[i - 1] * seed;

    sum[len] = 0;

    for (int i = len - 1; i >= 0; i--)sum[i] = sum[i + 1] * seed + T[i];

}

inline unsigned long long sub(int l, int r)

{

    return sum[l] - sum[r + 1] * expr[r - l + 1];

}

int main()

{

    memset(dp, 0x3F, sizeof(dp));

    cin >> T;

    len = T.length();

    init();

    for (int i = 0; i<len; i++)

    {

        dp[i][i][i] = 2;

    }

    for (int l = 2; l <= len; l++)

    {

        for (int i = 0; i <= len - l; i++)

        {

            int j = i + l - 1;

            dp[i][j][i] = l + 1;

            //当前区间、第二个区间最后一次断开的位置

            for (int k = i + 1; k <= j; k++)

            {

                //第一个区间的最后一次断开位置

                for (int cut1 = i; cut1 <= k; cut1++)

                {

                   //第二个区间没有被分割

                   dp[i][j][cut1] = min(dp[i][j][cut1],dp[i][k][cut1]+j-k);

                   //第一、二个区间的分割位置

                   for (int cutm = cut1; cutm <= min(k, j - 1); cutm++)

                   {

                       dp[i][j][k] = min(dp[i][j][k], dp[i][cutm][cut1] + dp[cutm + 1][j][k]);

                       if (sub(cut1, cutm) == sub(cutm + 1, j))dp[i][j][cut1] = min(dp[i][j][cut1], dp[i][cutm][cut1] + 1);

                   }

                }

            }

        }

    }

    int ans = dp[0][len - 1][0];

    for (int i = 1; i<len; i++)

    {

        ans = min(ans, dp[0][len - 1][i]);

    }

    cout << ans - 1 << endl;

    return 0;

}