NYOJ 1067 Compress String(구간 dp)

Compress String

시간 제한:
2000ms | 메모리 제한:
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)로 압축할 수 있다. 압축된 문자열을 계속 압축할 수 있다면 계속 압축할 수 있다. 예를 들어nowletsgogogogoandrunrunrun을 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][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;
}