NYOJ 1067 Compress String（区间dp）

Compress String

时间限制：2000 ms  |  内存限制：65535 KB

难度：3

描写叙述

One day,a beautiful girl ask LYH to help her complete a complicated task—using a new compression method similar to Run Length Encoding(RLE) compress a string.Though the task is difficult, LYH is glad to help her.

The compress rules of the new method is as follows: if a substring S is repeated k times, replace k copies of S by k(S). For example, letsgogogo is compressed into lets3(go). The length of letsgogogo is 10, and the length of lets3(go) is 9. In general, the length of k(S) is (number of digits in k ) + (length of S) + 2. For example, the length of 123(abc) is 8. It is also possible that substring S is a compressed string. For example nowletsgogogoletsgogogoandrunrunrun could be compressed as now2(lets3(go))and3(run).

In order to make the girl happy, LYH solved the task in a short time. Can you solve it?

输入

Thera are multiple test cases.
Each test case contains a string, the length of the string is no more than 200, all the character is lower case alphabet.

输出

For each test case, print the length of the shortest compressed string.

例子输入

ababcd 
letsgogogo
nowletsgogogoletsgogogoandrunrunrun

例子输出

6
9
24

题意：给出一个长度不超过200的字符串。把这个字符串依照一定规则压缩，即能够把几个连续的同样子串压缩成一个串，比如能够把letsgogogo压缩为lets3(go)，压缩后的子串假设还能够继续压缩。则能够继续压缩，如能够将nowletsgogogoletsgogogoandrunrunrun压缩为now2(lets3(go))and3(run)。问经过压缩后这个字符串的最短长度是多少。

分析： 区间DP,dp[i][j]表示从i到j的字符串表示的最短长度。

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

          然后去推断当前子串能不能压缩。即是否由反复字符串组成，推断时仅仅需暴力枚举反复长度，去推断就可以。
          假设当前子串能够压缩,则dp[i][j] = min(dp[i][j], dp[i][i + len - 1] + 2 + digcount((j - i + 1) / len));。

          注意假设是数字，要用数字的位数表示添加的个数。而不是单纯的添加1.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210;
#define INF 0x3fffffff
char str[N];
int n, dp[N][N];

int digit_cnt(int x)
{
    int a = 0;
    while(x) {
        a++;
        x /= 10;
    }
    return a;
}

bool check(int l, int r, int len)
{
    if((r - l + 1) % len) return false;
    for(int i = l; i < l + len; i++) {
        for(int j = i + len; j <= r; j += len)
            if(str[i] != str[j]) return false;
    }
    return true;
}

int get_ans()
{
    int i, j, k;
    n = strlen(str+1);
    for(i = 1; i <= n; i++) dp[i][i] = 1;
    for(i = n - 1; i >= 1; i--) {
        for(j = i + 1; j <= n; j++) {
            dp[i][j] = INF;
            for(k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            for(int len = 1; len <= j-i+1; len++) {
                if(check(i, j, len)) {
                    dp[i][j] = min(dp[i][j], dp[i][i+len-1] + 2 + digit_cnt((j - i + 1) / len));
                }
            }
        }
    }
    return dp[1][n];
}

int main()
{
    while(~scanf("%s", str+1)) {
        printf("%d
", get_ans());
    }
    return 0;
}