UVALive - 3363 String Compression （区间DP）

题意：将一串字符串按照规定压缩后的最小的长度是多少

思路：在区间DP上，再注意一点就行了，就是可以考虑当自身能作为压缩的字符串的情况

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 210;
const int INF = 0x3f3f3f3f;

char str[MAXN];
int dp[MAXN][MAXN],n;

int check(int s,int t,int k){
    if ((t-s+1) % k != 0)
        return 0;
    for (int i = s+k; i <= t; i += k)
        for (int j = 0; j < k; j++)
            if (str[s+j] != str[i+j])
                return 0;
    return (t-s+1) / k;
}

int getnum(int x){
    if (x >= 0 && x <= 9)
        return 1;
    if (x >= 10 && x <= 99)
        return 2;
    return 3;
}

void solve(){
    for (int i = 0; i < n; i++)
        dp[i][i] = 1;
    int temp;
    for (int k = 2; k <= n; k++){
        for (int i = 0; i <= n-k; i++){
            dp[i][i+k-1] = INF;
            for (int j = i; j < i+k-1; j++)
                dp[i][i+k-1] = min(dp[i][i+k-1],dp[i][j]+dp[j+1][i+k-1]);
            for (int z = 1; z <= k/2; z++){
                int temp = check(i,i+k-1,z);
                if (temp)
                    dp[i][i+k-1] = min(dp[i][i+k-1],dp[i][i+z-1]+2+getnum(temp));
            }
        }
    }
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%s",str);
        n = strlen(str);
        solve();
        printf("%d\n",dp[0][n-1]);
    }
    return 0;
}

UVALive - 3363 String Compression （区间DP）

原文：http://blog.csdn.net/u011345136/article/details/18862661