【POJ 2176】Folding

【原题链接】传送门

【题面大意】

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

【题解思路】

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=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
*/