欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 1351 - String Compression

程序员文章站 2024-03-12 23:39:03
...

题意: 对于一个字符串中的重复部分可以进行缩写,例如”gogogo“可以写成“3(go)”,从6个字符变成5个字符。。"nowletsgogogoletsgogogoandrunrunruncould " 可以写成 "now2(lets3(go))and3(run)".现在问在这个规则下,问给定一个串的最短长度是多少?

思路:记忆化搜索 + 区间dp,设dp[n][m]表示字符串的第n到第m个字符的最短长度,那么状态转移方程就是:

dp[n][m] = min(dp[n][n + k]+dp[n+k+1][m],calNum(k) + 2 + dp[n][n + k - 1]);

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 222;
const int INF = 0x7fffffff;
char str[MAXN];
int dp[MAXN][MAXN];
int calNum(int n){
    int cnt = 0;
    while(n) cnt ++, n /= 10;
    return cnt;
}
bool check(int n, int m, int k){
    if((m - n + 1) % k) return false;
    for(int i = 0 ;i < k;i ++){
        for(int j = n + k ;j <= m; j += k){
            if(str[j+i] != str[n+i]) return false;
        }
    }
    return true;
}
int dfs(int n, int m){         //dp[n][m] = min(dp[n][k] + dp[k+1][m], calNum(k) + dp[n][n+k-1] + 2);
    if(n == m) return 1;
    if(dp[n][m]) return dp[n][m];
    dp[n][m] = INF;
    for(int i = 0; i <= m - n - 1; i ++){
        dp[n][m] = min(dp[n][m], dfs(n, n + i) + dfs(n + i + 1, m));
        if(check(n, m, i + 1)) dp[n][m] = min(dp[n][m], calNum((m - n + 1)/(i + 1)) + 2 + dfs(n, n + i));
    }
    return dp[n][m];
}
int main(){
    int n;
    freopen("in.cpp", "r", stdin);
    while(~scanf("%d", &n)){
        for(int i = 0;i < n;i ++){
            memset(dp, 0, sizeof(dp));
            scanf("%s", str);
            printf("%d\n", dfs(0, strlen(str)-1));
        }
    }
    return 0;
}