区间dp，记忆化搜就可以
st为原串
dp[p][q]存st[p]~st[q]的最优长度，f[p][q]存对应的最优串
从（0，len-1）开始搜，f[0][len-1]为所求ans，回溯条件为p==q
同前两个题思路极为类似，但是我发现这3个题放到一起真的非常的好，难度递进，依次难在地方就是状态转移的时候决策的寻找
而此题的决策不是很明确，可以理解为两个决策吧（大家都这么认为= =但我不怎么赞同）
1:当子串st[p~q]可以折叠
2:将st[p~q]分成两段
二者中取最短
（其实第二个决策隐藏了一个决策，举个例子，原串AA，而压缩成2（A）显然是不对的，根据第二个决策，dp[AA]=dp[A]+dp[A]=2优于决策1）
自己coding时遇到一个问题：
NTTTTTNTTTTTNTTTTT
根据决策2，会得到一种情况f[0][len-1]=2(N5(T))N5(T),怎么折叠成3(N5(T))；
若是根据决策1，那得到的结果会是3（NTTTTT）;
特殊处理嵌套会非常麻烦
解决方法详见代码
观察了网上其他人的代码，学到了不少东西
coding+debug：差不多断断续续5个小时左右（但是这5个小时是比较值的，记忆化dp或者说区间dp这一方面我理解的更具体，更深刻了）
/*
* Author: Bingo
* Created Time: 2015/3/3 14:19:57
* File Name: uva1630.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
using namespace std;
const int maxint = ;
int n;
int len;
string st;
int dp[][];
string f[][];//一层状态对应一个串
int judge(int l,int r){
for(int i=;i<=(r-l+)/;i++){
if((r-l+)%i)continue;
bool flag=true;
for(int j=l;j+i<=r;j++){
if(st[j]!=st[j+i]){
flag=false;
break;
}
}
if(flag)return i;
}
return false;
}
int solve(int p,int q){
if (dp[p][q]) return dp[p][q];
else if(p==q) {
f[p][q]=st[p];
dp[p][q]=;
return ;
}
else {
int ans=maxint;
int res;
int k;
for (int i=p;i<q;i++){
res=solve(p,i)+solve(i+,q);
if (ans>res){
ans=res;
k=i;
}
}
f[p][q]=f[p][k]+f[k+][q];//此时的f[p][q]是否可折叠等价于st[p] [q]是否可折叠，巧妙的解决折叠f[p][q]时提取公因式的困难
int t=judge(p,q);
if (t){
char tt[];
sprintf(tt,"%d",(q-p+)/t);
string newstr=tt+string("(")+f[p][p+t-]+string(")");//f[p][p+t-1]是精髓所在
if (newstr.size()<f[p][q].size()) f[p][q]=newstr;
}
dp[p][q]=f[p][q].size();
return dp[p][q];
}
}
int main () {
while (cin>>st){
len=st.size();
memset(dp,,sizeof(dp));
solve(,len-);
cout << f[][len-]<<endl;
}
return ;
}