uvalive 3363(区间dp)

题意：给出一个字符串，问最多能缩减到多短。缩减方式比如：
aaaaabbbb -> 5(a)4(b)
nowletsgogogoletsgogogo -> now2(lets3(go))
题解：区间dp，f[l][r]表示从l到r最多缩减到的长度。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 205;
char s[N];
int f[N][N], hehe[N][N];

bool judge(int st, int num, int len) {
    for (int i = st; i < st + len; i++)
        for (int j = 1; j < num; j++) {
            if (s[i] != s[i + j * len])
                return false;
        }
    return true;
}

int Count(int num) {
    int cnt = 0;
    while (num) {
        num /= 10;
        cnt++;
    }
    return cnt;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s);
        int len = strlen(s);
        for (int i = 0; i < len; i++)
            for (int j = 0; j < len; j++) {
                hehe[i][j] = f[i][j] = j - i + 1;
            }
        for (int i = 2; i <= len; i++) { //length
            for (int j = 0; j + i - 1 < len; j++) { //start
                int l = i / 2;
                for (int k = 1; k <= l; k++) {
                    if (i % k)
                        continue;
                    if (judge(j, i / k, k)) {
                        if (f[j][j + i - 1] > Count(i / k) + 2 + k) {
                            f[j][j + i - 1] = Count(i / k) + 2 + k;
                            hehe[j][j + i - 1] = k;
                        }
                        break;
                    }
                }
            }
        }
        for (int i = 1; i < len; i++)
            for (int j = 0; j + i < len; j++) {
                if (f[j][j + i] == i + 1) {
                    for (int k = j; k < j + i; k++)
                        f[j][j + i] = min(f[j][k] + f[k + 1][j + i], f[j][j + i]);
                }
                else {
                    int l = hehe[j][j + i], temp = f[j][j + i];
                    for (int k = 1; k < l; k++)
                        for (int m = j; m + k < j + l; m++)
                            if (f[m][m + k] != k + 1)
                                f[j][j + i] = min(f[j][j + i], temp - (k + 1 - f[m][m + k]));
                }
            }
        printf("%d\n", f[0][len - 1]);
    }
    return 0;
}