记忆化搜索很简单，就是用的时候老是想不到~~无奈的感觉~~~
dp[l][r] :l到r这一段中的最小表示方法。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INT_MAX 0x7fffffff
#define maxn 101
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
string str;
string dp[maxn][maxn];
string s,ss;
string ns(int x)
{ss="";if(x>=100)ss.push_back(x/100+'0');if(x>=10)ss.push_back((x/10)%10+'0');if(x>0)ss.push_back(x%10+'0');return ss;
}
int pan(int l,int r,int x)
{for(int i=l+x;i<=r;i++){if(str[i]!=str[i-x])return 0;}return 1;
}
string dfs(int l,int r)
{int t;int i;if(dp[l][r]!="")return dp[l][r];if(l==r){dp[l][r].push_back(str[l]);return dp[l][r];}s="";for(i=l;i<=r;i++){dp[l][r].push_back(str[i]);}int len=dp[l][r].size();int fn;for(i=1;i<=len/2;i++){if((r-l+1)%i)continue;if(!pan(l,r,i))continue;t=(r-l+1)/i;fn=1;if(t>9)fn=2;if(t>99)fn=3;s=dfs(l,l+i-1);if(s.size()+2+fn<dp[l][r].size()){dp[l][r]=ns(t)+"("+s+")";}}for(i=l;i<r;i++){if(dfs(l,i).size()+dfs(i+1,r).size()<dp[l][r].size()){dp[l][r]=dp[l][i]+dp[i+1][r];}}return dp[l][r];
}
int main()
{while(cin>>str){for(int i=0;i<101;i++){for(int j=0;j<101;j++)dp[i][j]="";}cout<<dfs(0,str.size()-1)<<endl;}return 0;
}