forked from sukhoeing/aoapc-bac2nd-keys
-
Notifications
You must be signed in to change notification settings - Fork 0
/
UVa1630.cc
60 lines (53 loc) · 1.41 KB
/
UVa1630.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Folding, ACM/ICPC NEERC 2001, UVa1630
// 陈锋
#include <iostream>
#include <string>
#include <climits>
#include <cassert>
#include <sstream>
#define _for(i,a,b) for( int i=(a); i<(b); ++i)
#define _rep(i,a,b) for( int i=(a); i<=(b); ++i)
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 104;
string S, Fold[MAXN][MAXN];
int getMinCycle(int l, int r){
int segLen = r-l+1;
_rep(cycle, 1, segLen/2){
if(segLen%cycle) continue;
bool flag = true;
_rep(j, l, r-cycle){
if(S[j] == S[j+cycle]) continue;
flag = false;
break;
}
if(flag) return cycle;
}
return 0;
}
string& solve(int l, int r){
string& ans = Fold[l][r];
if(!ans.empty()) return ans;
if(l == r) return ans = S[l];
int minK, ansLen = INF;
_for(i, l, r){
int len = solve(l,i).size() + solve(i+1, r).size();
if(len < ansLen) minK = i, ansLen = len;
}
ans += solve(l, minK);
ans += solve(minK+1, r);
int cycle = getMinCycle(l, r);
if(cycle){
stringstream ss;
ss<<(r-l+1)/cycle<<"("<<solve(l, l+cycle-1)<<")";
if(ss.tellp() < ans.size()) ss>>ans;
}
return ans;
}
int main(){
while(cin>>S){
int n = S.size();
_for(i, 0, n) _for(j, 0, n) Fold[i][j].clear();
cout<<solve(0, n-1)<<endl;
}
}
// 1992297 2692 Folding Accepted C++11 0.062 2016-07-20 09:47:42