分折叠和合并两个方案进行转移。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=205;
struct node{int len;char s[N];}f[N][N];
char s[N];
int main()
{
    scanf("%s",s+1);int n=strlen(s+1);
    for(int i=1;i<=n;i++)f[i][i].len=1,f[i][i].s[0]=s[i];
    for(int k=2;k<=n;k++)
        for(int i=1;i<=n-k+1;i++)
        {
            int j=i+k-1;f[i][j].len=0x3f3f3f3f;
            for(int l=1;l<=k/2;l++)//压缩 
            {
                if(k%l!=0)continue;
                int st=i,ed=i+l;
                while(ed<=j&&s[st]==s[ed])++ed,++st;
                if(ed>j)
                {
                    int num=k/l;
                    sprintf(f[i][j].s,"%d",num);
                    strcat(f[i][j].s,"(");
                    strcat(f[i][j].s,f[i][i+l-1].s);
                    strcat(f[i][j].s,")");
                    f[i][j].len=strlen(f[i][j].s);
                    break;
                }
            }
            for(int mid=i;mid<j;mid++)//合并 
                if(f[i][j].len>f[i][mid].len+f[mid+1][j].len)
                {
                    f[i][j].len=f[i][mid].len+f[mid+1][j].len;
                    strcpy(f[i][j].s,f[i][mid].s);
                    strcat(f[i][j].s,f[mid+1][j].s);
                }
        }
    printf("%s",f[1][n].s);
    return 0;
}