【原题链接】传送门
【题面大意】
一个字符串，可以将它改写成循环节带括号的形式进行压缩，输出压缩长度最小的字符串。
【题解思路】
1.没思路没思路，不知道怎么乱搞，大概就可以想到动态规划。
2.套路区间dp，f[l][r]表示[l,r]区间内的最小表示（字符串）和长度。
3.考虑需要进行的两个操作：折叠和合并。
折叠：每次扫描区间来求循环节感觉不是很行。->枚举折叠后的循环节的长度
合并：枚举中心点，注意长度和字符串都要更新。
4.注意边界：枚举循环节时 ，如果超出r的范围，当前长度就可作为循环节的长度。
注意初值：因为要求最小值，初值设为无穷大。
5.学到的：几个函数的用法。如：
strcat(d,s); // d = d+s;
strcpy(a,b); // 将b字符串复制到a中
sprintf(f,"类型"，d); // 将任意类型d的字符写入f中
【code】
#include<bits/stdc++.h>
using namespace std;
#define File ""
#define inf 1<<30
#define ll long long
#define ull unsigned long long
#define rep(k,i,j) for(int k = i;k <= j; ++k)
#define FOR(k,i,j) for(int k = i;k >= j; --k)
inline void file(){
freopen(File".in","r",stdin);
freopen(File".out","w",stdout);
}
inline int read(){
int x=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-''; ch=getchar();}
return x*f;
}
const int mxn = +;
char ch[mxn];
int n;
struct rec{int lth; char s[mxn];}f[mxn][mxn];
int main(){
// file();
scanf("%s",ch+);
n = strlen(ch+);
rep(i,,n) f[i][i].s[] = ch[i],f[i][i].lth = ;
rep(len,,n){
rep(l,,n-len+){
int r = l+len-;
f[l][r].lth = inf;
rep(i,,len>>){
if(len%i) continue;
int st = l,ed = l+i;
while(ch[st] == ch[ed] && ed<=r) st++,ed++;
if(ed > r){
sprintf(f[l][r].s,"%d",len/i),
strcat(f[l][r].s,"("),
strcat(f[l][r].s,f[l][l+i-].s),
strcat(f[l][r].s,")");
f[l][r].lth = strlen(f[l][r].s);
break;
}
}
rep(i,l,r-){
if(f[l][r].lth > f[l][i].lth + f[i+][r].lth){
f[l][r].lth = f[l][i].lth + f[i+][r].lth;
strcpy(f[l][r].s,f[l][i].s);
strcat(f[l][r].s,f[i+][r].s);
}
}
}
}
puts(f[][n].s);
return ;
}
/*
AAAAAAAAAABABABCCD
*/