uva 1351 String Compression（dp)

題意：給一個字元串，如果其中有m個子串s0相等的話，可以表示為m(s0)，然後問給定字元串最少可以表示成多少？

思路：設d[i][j]為i~j字元串最小長度是多少。則d[i][j] = min{d[i][k]+d[k][j]}，還要考慮自身存在循環的子串，則枚舉s0的長度，d[i][j] = min(d[i][j],d[i][i+k-1] + 2 + cal(j-i+1)/k);

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mem(name,value) memset(name,value,sizeof(name))
#define FOR(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int maxn = 200+10;
const int inf = 0x3f3f3f3f;
int d[maxn][maxn];
char s[maxn];
int cal(int x){
    int ans = 0;
    while(x){
        x/=10;
        ans++;
    }
    return ans;
}
bool judge(int l,int r,int k){
    if((r-l+1)%k!=0) return false;
    for(int i=l;i<l+k;i++)
        for(int j=i+k;j<=r;j+=k) if(s[j]!=s[i])
            return false;
    return true;
}
int main(){
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%s",s+1);
        mem(d,inf);
        int n = strlen(s+1);
        for(int i=0;i<=n;i++) d[i][i] = 1;

        for(int i=n;i>=1;i--)
        for(int j=i;j<=n;j++){
            for(int k=i;k<j;k++)
                d[i][j] = min(d[i][j],d[i][k]+d[k+1][j]);
            int len = j-i+1;
            for(int k=1;k<len;k++) if(judge(i,j,k)){
                d[i][j] = min(d[i][j],d[i][i+k-1]+cal(len/k)+2);
            }
        }
        printf("%d\n",d[1][n]);
    }
    return 0;
}