wa on #6#13#16.
UVA上的双倍经验都过了，所以看来是字典序最大的问题.

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
	#ifndef LOCAL
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	inline long long read(){char ch=gh();long long x=0;bool t=0;while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();return t?-x:x;}
	inline void write(int x){static int sta[35];int top = 0;do{sta[top++] = x % 10, x /= 10;} while (x);while (top)putchar(sta[--top] + 48);}
	const void File(bool b1,bool b2){if(b1)freopen("out.out","w",stdout);if(b2)freopen("in.in","r",stdin);}
	
}
using namespace IO;
string s;
int n;
char A[105];
int dp[105][105],mid[105][105];

int getlen(int x){
    int res=0;
    while(x){
        res++,x/=10;
    }
    return res;
}
struct node{
    int typ,rep;//typ=1->从头到尾缩掉了并带有数字.
    int l,r,len,cst;//l,r->循环节
    int tim,truc=0;
    node(){}
    node(int _l,int _r){
        l=_l,r=_r,rep=0,tim=1;
        //len=r-l+1;
        len=dp[l][r];
        cst=len+2+getlen(tim);
    }
    node(int _l,int _r,int _tim){
        l=_l,r=_r,rep=0,tim=_tim;
        len=dp[l][r];
        cst=len+2+getlen(tim);
    }
}fr[105][105];
#define cur fr[i][i+k]
bool equ(int l1,int r1,int l2,int r2){
    if(r1-l1!=r2-l2)return 0;
    for(int i=l1,j=l2;i<=r1;i++,j++){
        if(A[i]!=A[j])return 0;
    }return 1;
}

void output(int l,int r){
    if(r<l)return;
    if(r==l){cout<<A[l];return;}
    if(fr[l][r].tim>1 and fr[l][r].cst==dp[l][r] and dp[l][r]<r-l+1){
        cout<<fr[l][r].tim<<'(';
        output(fr[l][r].l,fr[l][r].r);
        cout<<')';
        return;
    }
    if(fr[l][r].truc){
        output(l,fr[l][r].truc);
        output(fr[l][r].truc+1,r);
        return;
    }
    for(int i=l;i<=r;i++)cout<<A[i];
}
int main(){
    cin>>s;
    n=s.size();
    for(int i=1;i<=n;i++)A[i]=s[i-1];
    for(int i=1;i<=n;i++){
        dp[i][i]=1;
        fr[i][i]=node(i,i);
    }
    for(int k=1;k<n;k++){
        for(int i=1;i<=n-k;i++){//[i,i+k].
            dp[i][i+k]=k+1;
            fr[i][i+k]=node(i,i+k);
            int l=i,r=i+k;
            for(int j=i;j<i+k;j++){//从这个位置分割开，让两边的相匹配.
                node u=fr[i][j],v=fr[j+1][i+k];
                if(equ(u.l,u.r,v.l,v.r)){
                    int tn=(u.tim+v.tim),xn=2+(dp[u.l][u.r])+getlen(tn);
                    if(dp[i][i+k]>=xn){
                        dp[i][i+k]=xn;
                    }
                    cur=node(u.l,u.r,tn);//fr中的是强制匹配的结果，而dp是最小结果.
                }
                if(dp[i][j]+dp[j+1][i+k]<dp[i][i+k]){
                    dp[i][i+k]=dp[i][j]+dp[j+1][i+k];
                    cur=node(i,i+k);
                    cur.truc=j;
                }
            }

        }
    }
    output(1,n);
}