压缩字符串题解

输入一个仅由大写字母组成的字符串（长度不超过100），可以用如下规则压缩：

1. 如果遇到连续的重复字串，可以只保留一个，在其两边用"n(",")"标记，n表示重复的次数。
2. 括号的使用可以嵌套。

使用以上规则，尽可能压缩字符串（即使压缩后的串尽量短），输出压缩结果。

比如：
AAAAAAAAA           ->    9(A)
AAAAAABBBBBB    ->     6(A)6(B)
AA                          ->     AA
ICICICICICI              ->     4(IC)I
AAAAABBBBBAAAAABBBBB   ->     2(5(A)5(B))

这是一题的最优子结构性质非常明显，是典型的区间动态规划题。
用f[i][j]表示i~j这个字符串最小的长度。
显然，
f[i][j] = min{j - i + 1,f[i][k] + f[k + 1][j],compress(f[i][j])}
i<=k由于需要输出字符，因此增加一个s[i][j][MAXLEN]记录str[i]~str[j]压缩后的情况。

s[0][len - 1]就是最终结果。

需要注意，动态规划的特性决定了它会对所有可能的情况作出转移并选择最优的。因此在写动规方程的时候要注意避免没有必要的转移（或者重复的转移）。

?

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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXLEN 101 char str[MAXLEN]; int len; char s[MAXLEN][MAXLEN][MAXLEN] = {}; int f[MAXLEN][MAXLEN]; int numlen(int x) {     if(x >= 100)   return 3;     if(x >= 10)    return 2;     return 1; } void output() {     int i;     for(i = 0;i < f[0][len - 1];i ++)         printf("%c",s[0][len - 1][i]);     printf("\n"); } int find(int b,int l,int e) {     int i,r = 1;     for(i = b + l;i <= e - l + 1;i += l)     {         if(strncmp(str + b,str + i,l) != 0)   return 0;         r ++;     }     return r; } void solve() {     int l,j,k,i,seg;     int r,newlen;     char tmp[MAXLEN];     for(i = 0;i < len;i ++)         for(j = i;j < len;j ++)         {             f[i][j] = j - i + 1;             memcpy(s[i][j],str + i,j - i + 1);         }     for(l = 2;l <= len;l ++)         for(i = 0;i < len;i ++)         {             j = l + i - 1;             if(j >= len)   break;             for(seg = 1;seg < l;seg ++)                 if(l % seg == 0)                 {                     r = find(i,seg,j);                     if(r == 0)    continue;                     newlen = numlen(r) + 2 + f[i][i + seg - 1];   //寻找重复串                     if(newlen < f[i][j])                     {                         f[i][j] = newlen;                         sprintf(s[i][j],"%d(",r);                         strcat(s[i][j],s[i][i + seg - 1]);                         strcat(s[i][j],")");                     }                 }             for(k = i;k < j;k ++)             {                 if(f[i][k] + f[k + 1][j] < f[i][j])                 {                     f[i][j] = f[i][k] + f[k + 1][j];                     strcpy(s[i][j],s[i][k]);                     strcat(s[i][j],s[k+1][j]);                 }             }             //fprintf(stderr,"(%d,%d):%s\n",i,j,s[i][j]);         } } int main() {     freopen("cipher.out","w",stdout);     freopen("cipher.in","r",stdin);     scanf("%s\n",str);     len = strlen(str);     solve();     output();     fclose(stdout);     return 0; }