uva1630（dp記憶化搜尋）

/*
translation:
	将一串字元串折疊成一串盡量短的字元串
solution:
	記憶化搜尋dp
	可以看出一串字元串有3種情況：
	1.字元串本身就已經是最簡短
	2.可以折疊成某一個更短的字元串
	3.隻有一部分能夠折疊成更短的字元串，這時需要分成兩部分來求解，需要周遊來确定拆分的位置
	根據以上3種情況即可編碼
note:
	* 字元串折疊類型的題可以考慮區間dp和記憶化搜尋
	# check方法裡面的第二重循環的範圍錯誤了，應該是i+len<=e，而不是i+len-1<=e
date:
	2017.1.15
*/
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 100 + 5;
const int INF = 1e8;

int dp[maxn][maxn];	//dp[a][b]代表字元串[a,b]區間上折疊後的最小長度是多少
string ans[maxn][maxn], str;	//ans[a][b]代表區間[a,b]的答案

int check(int s, int e)
{
	for(int len = 1; len <= (e-s+1)/2; len++){	//周遊長度
		if((e - s + 1) % len)	continue;
		bool flag = true;
		for(int i = s; i + len <= e; i++){
			if(str[i] != str[i+len]){
				flag = false;
				break;
			}
		}
		if(flag)	return len;
	}
	return 0;
}

int solve(int s, int e)
{
	if(dp[s][e] != -1)	return dp[s][e];
	if(s == e){
		ans[s][e] = str[s];
		return dp[s][e] = 1;
	}

	int len = INF, pos;				//分成左右兩部分求解
	for(int m = s; m < e; m++){
		int temp = solve(s, m) + solve(m+1, e);
		if(temp < len){
			len = temp;
			pos = m;	//找到拆分成2部分的位置
		}
	}
	ans[s][e] = ans[s][pos] + ans[pos+1][e];

	int l = check(s, e);			//按照折疊方式來求解
	if(l){
		char num[20];
		sprintf(num, "%d", (e - s + 1) / l);
		string t = num + string("(") + ans[s][s+l-1] + string(")");
		if(t.length() < len){
			ans[s][e] = t;
			len = t.length();
		}
	}
	return dp[s][e] = len;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	while(cin >> str){
		int len = str.length();
		memset(dp, -1, sizeof(dp));

		solve(0, len-1);
		cout << ans[0][len-1] << endl;
	}
	return 0;
}