一道别样的区间dp，重点在于对字符串的处理。
读完题，我们很自然的想到区间dp，定义f[i][j]表示从折叠i~j的部分的最小长度，那么答案为f[1][n]。
区间dp的转移一般而言都是一样的，在区间中枚举一个位置，使这一个大区间分成两个小区间。因此状态转移方程我们不在赘述。
我们重点探讨一下对于字符串的处理，首先我们枚举区间的长度，左端点（右端点可以求出），这是区间dp的基本方法，之后我们枚举折叠成每一段的长度，显然区间的长度一定是每一段长度的正整数倍，之后我们在判断一下把这个区间分成这么多段之后每一段是否相同，如果相同，则表明可以折叠。我们将折叠之后的字符串覆盖元原区间的字符串。具体地，我们用一个结构体表示一个状态，结构体中有两个元素，一个表示字符串的长度，另一个表示字符串。因此算法就这样设计完成了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define inf 1e9 7 typedef long long ll; 8 struct node { 9 int len; 10 char s[110]; 11 }f[110][110]; 12 int n; 13 char s[110]; 14 int main() { 15 scanf("%s",s+1); 16 n=strlen(s+1); 17 for(int i=1;i<=n;i++) { 18 f[i][i].len=1; 19 f[i][i].s[0]=s[i]; 20 } 21 for(int l=2;l<=n;l++) { 22 for(int i=1;i+l-1<=n;i++) { 23 int j=i+l-1; 24 f[i][j].len=inf; 25 for(int k=1;k<=l/2;k++) { 26 if(l%k) continue ; 27 int x=i,y=i+k; 28 while(s[x]==s[y]&&y<=j) x++,y++; 29 if(y>j) { 30 int num=l/k; 31 sprintf(f[i][j].s,"%d",num); 32 strcat(f[i][j].s,"("); 33 strcat(f[i][j].s,f[i][i+k-1].s); 34 strcat(f[i][j].s,")"); 35 f[i][j].len=strlen(f[i][j].s); 36 break ; 37 } 38 } 39 for(int k=i;k<j;k++) { 40 if(f[i][j].len>f[i][k].len+f[k+1][j].len) { 41 f[i][j].len=f[i][k].len+f[k+1][j].len; 42 strcpy(f[i][j].s,f[i][k].s); 43 strcat(f[i][j].s,f[k+1][j].s); 44 } 45 } 46 } 47 } 48 puts(f[1][n].s); 49 return 0; 50 }