UVALive - 3363 String Compression 區間DP

UVALive - 3363 String Compression 區間DP

題目大意：有一串字符串，現在有一種轉換規則，如果字符串中出現循環的子串，可以將其轉化為 :子串數量(子串)
現在問這個字符串的最短長度

解題思路：區間dp，然後分類討論，這題的難點是如何再進行縮減
將情況分為兩種
一種是區間剛好符合縮減情況的，找出該區間的循環節，看能否繼續縮減即可
另一種情況就是普通的區間DP了
以下是一個錯誤的代碼，因為少考慮了其他的縮減情況。
以下代碼只考慮了一個能縮減的子串再縮減一個子串的情況，沒有考慮到縮減多個子串的情況，比如letsgogogoaaaaaaaletsgogogoaaaaaaaaletsgogogoaaaaaaaa這種情況，以下代碼只考慮了縮減letsgogogoaaaaaaaa中的gogogo或者aaaaaaaa而已，沒有考慮到同時縮減，所以是錯的，但UVA能過，樣例強度不夠

錯誤的但能A的代碼

#include
#include
#include
using namespace std;
#define maxn 210
#define INF 0x3f3f3f3f
char str[maxn];
int dp[maxn][maxn];
int vis[maxn][maxn];
int d;

int solve(int s, int e) {
    int len = (e - s + 1) / 2;
    bool mark = true;
    int ans, i;
    for(i = 1; i <= len; i++) 
        if((e - s + 1) % i == 0) { 
            mark = false;
            for(int j = 0; j < i; j++) { 
                char t = str[s + j];
                for(int k = s + j; k <= e; k += i)
                    if(str[k] != t) {
                        mark = true;
                        break;
                    }
                if(mark)
                    break;
            }
            if(!mark) {
                ans  = i;
                d = i;
                break;
            }
        }

    if(!mark) {
        int length;
        if( (e - s + 1) / ans >= 100)
            length = 3;
        else if( (e - s + 1) / ans >= 10)
            length = 2;
        else
            length = 1;

        if(length + 2 + i <= (e - s + 1))  
            return length + 2 + i; 
        else 
            return (e - s + 1);
    }
    else 
        return (e - s + 1);
}

int main() {
    int test;
    scanf(%d, &test);
    while(test--) {
        scanf(%s, str + 1);
        int len = strlen(str + 1);
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= len; i++)
            dp[i][i] = 1;
        for(int i = 1; i < len; i++)
            for(int j = 1; j + i <= len; j++) {
                int e = j + i;
                dp[j][e] = solve(j,e);  
                if(dp[j][e] == (e - j + 1))
                    for(int k = j; k < e; k++) 
                        dp[j][e] = min(dp[k + 1][e] + dp[j][k], dp[j][e]);
                else {
                    vis[j][e] = 1;
                    int t = dp[j][e], Min = dp[j][e];
                    for(int duan = 3; duan < d; duan++)
                        for(int start = j; start + duan < j + d; start++) {
                            if(vis[start][start + duan]) {
                                Min = min(Min, t - (duan + 1) + dp[start][start + duan]);
                            }
                        }
                    dp[j][e] = Min;
                }
            }
        printf(%d
, dp[1][len]);
    }
    return 0;
}

改過的代碼，如果還有錯，還望指出

#include
#include
#include
using namespace std;
#define maxn 210
#define INF 0x3f3f3f3f
char str[maxn];
int dp[maxn][maxn];
int vis[maxn][maxn];
int d, length;

int solve(int s, int e) {
    int len = (e - s + 1) / 2;
    bool mark = true;
    int ans, i;
    for(i = 1; i <= len; i++) 
        if((e - s + 1) % i == 0) { 
            mark = false;
            for(int j = 0; j < i; j++) { 
                char t = str[s + j];
                for(int k = s + j; k <= e; k += i)
                    if(str[k] != t) {
                        mark = true;
                        break;
                    }
                if(mark)
                    break;
            }
            if(!mark) {
                ans  = i;
                d = i;
                break;
            }
        }

    if(!mark) {
        if( (e - s + 1) / ans >= 100)
            length = 3;
        else if( (e - s + 1) / ans >= 10)
            length = 2;
        else
            length = 1;

        if(length + 2 + i <= (e - s + 1))  
            return length + 2 + i; 
        else 
            return (e - s + 1);
    }
    else 
        return (e - s + 1);
}

int main() {
    int test;
    scanf(%d, &test);
    while(test--) {
        scanf(%s, str + 1);
        int len = strlen(str + 1);
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= len; i++)
            dp[i][i] = 1;
        for(int i = 1; i < len; i++)
            for(int j = 1; j + i <= len; j++) {
                int e = j + i;
                dp[j][e] = solve(j,e);  
                if(dp[j][e] == (e - j + 1))
                    for(int k = j; k < e; k++) 
                        dp[j][e] = min(dp[k + 1][e] + dp[j][k], dp[j][e]);
                else {
                    dp[j][e] =  min(dp[j][e], length + 2 + dp[j][j + d - 1]);
                }
            }
        printf(%d
, dp[1][len]);
    }
    return 0;
}