【题面大意】

一个字符串，可以将它改写成循环节带括号的形式进行压缩，输出压缩长度最小的字符串。

【题解思路】

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
      
       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=0,f=1;   char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1; ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}    return x*f;}const int mxn = 100+5;char ch[mxn];int n;struct rec{
    int lth; char s[mxn];}f[mxn][mxn];int main(){//    file();    scanf("%s",ch+1);    n = strlen(ch+1);    rep(i,1,n) f[i][i].s[0] = ch[i],f[i][i].lth = 1;    rep(len,2,n){        rep(l,1,n-len+1){            int r = l+len-1;            f[l][r].lth = inf;            rep(i,1,len>>1){                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-1].s),                    strcat(f[l][r].s,")");                    f[l][r].lth = strlen(f[l][r].s);                    break;                }            }            rep(i,l,r-1){                if(f[l][r].lth > f[l][i].lth + f[i+1][r].lth){                    f[l][r].lth = f[l][i].lth + f[i+1][r].lth;                    strcpy(f[l][r].s,f[l][i].s);                    strcat(f[l][r].s,f[i+1][r].s);                }            }        }    }    puts(f[1][n].s);    return 0;}/*AAAAAAAAAABABABCCD*/