hihoCoder#1320：压缩字符串

是一个递归问题，根据讨论区提示，分为三种情况取最短。
来自：https://hihocoder.com/discuss/question/4635

本题是一道非常经典的动态规划题目。
设S[1..n]是一个长度为n的字符串，best(S)是S的最短压缩，那么best(S)可能为三种形式中最短的一种：

1. 原串形式：best(S) = S。例如CCD最短压缩就是CCD本身。
2. 拼接形式： best(S[1..n]) = best(S[1..i]) + best(S[i+1..n])。
   例如AAAAAAAAAABABABCCD的最短压缩9(A)3(AB)CCD，可以视为由best(AAAAAAAAAABABAB) = 9(A)3(AB) 和 best(CCD) = CCD 拼接而成。
3. 嵌套形式： best(S[1..n]) = k的位数 + 2 + best(S[1..n/k])，其中k>1且是n的约数，S是由k个S[1..n/k]循环拼接而成。也就是说S[1..n]可以表示成k(s[1..n/k])，这时k(s[1..n/k])的长度是k的位数 + 一对括号的长度2 + best(S[1..n/k])

#include <iostream>
#include <math.h>
using namespace std;

int best[100][100];

int calbest(string s)
{
    int n = s.size();
    for(int i = 0; i < n; i++)
    {
        best[i][i] = 1;
    }
    for(int j = 0; j < n; j++)
    {
        for(int i = j - 1; i >= 0; i--)
        {
            int nowbest = j - i + 1; //初始原长，情况一
            int nowlen = j - i + 1;

            //情况二
            for(int k = i; k < j; k++)
                nowbest = min(nowbest, best[i][k] + best[k + 1][j]);

            //情况三
            for(int k = i; k < j; k++)
            {
                if(s[k] == s[j])
                {
                    int onelen = k - i + 1;
                    if(nowlen % onelen == 0)
                    {
                        string onestr = s.substr(i, onelen);
                        int p = k;
                        while(p < j && s[p + 1] == onestr[(p - i + 1) % onelen]) p++;
                        if(p == j)
                            nowbest = min(nowbest, int(ceil(log10(nowlen / onelen + 1))) + 2 + best[i][k]);
                    }
                }
            }
            best[i][j] = nowbest;
        }
    }
    return best[0][n - 1];
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        string s;
        cin >> s;
        cout << calbest(s) << endl;
    }
    return 0;
}