题意: 将字符串压缩到最短。压缩规则见题目。
分析: 这题我就是用了最原始的方法了。一段一段来压缩。即现在要压缩[i,j]这一段时，要保证任意一段长度比j-i+1小的压缩结果都已经得出来了，也就是按长度从小到大来dp。压缩[i,j]的方法有两种，一种压缩成"数字(字符串)"的形式，另一种是压缩成[i,k][k+1,j]的形式。比较一下，哪种短就选哪种了。
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
#define inf 200000000

struct node
{
    int len;
    char ss[110];
}f[110][110];

char ts[110];
int pos;

void tostring(int num)
{
    char cc;
    int i;
    pos=-1;
    while(num)
    {
        ts[++pos]=(num%10)+'0';
        num/=10;
    }
    for(i=0;i<=pos/2;i++)
    {
        cc=ts[i]; ts[i]=ts[pos-i]; ts[pos-i]=cc;
    }
}

int main()
{
    int i,j,k,nlen,now,p,q,n,num;
    char s[110];
    while(scanf("%s",s+1)!=EOF)
    {
        n=strlen(s+1);
        for(i=1;i<=n;i++)   // 初始化
        {
            f[i][i].ss[0]=s[i];
            f[i][i].ss[1]='\0';
            f[i][i].len=1;
        }
        for(nlen=2;nlen<=n;nlen++)   // 现在的长度
        {
            for(i=1;i+nlen-1<=n;i++)
            {
                j=i+nlen-1; 
                f[i][j].len=inf;
                //  先看能不能压缩成"数字(字符串)"的形式
                for(now=1;now<nlen;now++)   // now---想折叠成的长度
                {
                    if(nlen%now) continue;
                    q=i+now; p=i;
                    while(q<=j)
                    {
                        if(s[q]!=s[p]) break;
                        p++; q++;
                        if(p==i+now) p=i;
                    }
                    if(q>j)     // 可以压缩成"数字(字符串)"的形式
                    {
                        num=nlen/now;
                        tostring(num);
                        strcpy(f[i][j].ss,ts);
                        f[i][j].ss[++pos]='(';
                        for(p=0;f[i][i+now-1].ss[p];p++) f[i][j].ss[++pos]=f[i][i+now-1].ss[p];
                        f[i][j].ss[++pos]=')';
                        f[i][j].len=pos+1;
                        f[i][j].ss[++pos]='\0';
                        break;
                    }
                }
                for(k=i;k<j;k++)  // [i,k][k+1,j]这种形式
                {
                    if(f[i][k].len+f[k+1][j].len<f[i][j].len)
                    {
                        f[i][j].len=f[i][k].len+f[k+1][j].len;
                        strcpy(f[i][j].ss,f[i][k].ss);
                        strcat(f[i][j].ss,f[k+1][j].ss);
                    }
                }
            }
        }
        printf("%s\n",f[1][n].ss);
    }
    return 0;
}