Solution
这种字符串题一般都是区间 dp，设 \(f(i,j)\) 表示第 \(i\) 到 \(j\) 的子串的最小长度，如果没有折叠操作，则枚举断点 \(k\)，转移方程为：
\[f(i,j)=\min(f(i,j),f(i,k)+f(k+1,j)) \]若有折叠操作，这时想要折叠就必须满足整段是一个循环，所以我们枚举循环节长度，用 hash 判断是否是循环节，若是，则转移方程如下：
\[f(i,j)=\min(f(i,j),f(i,k)+2+t(len/l)) \]其中加 \(2\) 表示括号，\(len\) 是我们枚举的子串长度，\(l\) 是循环节长度，\(t\) 数组表示某个整数占的位数。
补充
hash 判循环节的方式如下：
如图，\(l\) 是我们枚举的循环节长度，蓝色线段是我们需要判断的，黄色部分的长度为 \(l\)，若蓝色线段的 hash 值相等，则有 ① 等于 ③，而 ③ 又等于 ②，像这样就可以像推多米诺骨牌一样把后面的全部判断成相等，即可判断循环节。
此算法判断一个段是否为循环节是 \(O(1)\) 的，非常高效。
Code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
void read(int &x)
{
char ch=getchar();
int r=0,w=1;
while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
x=r*w;
}
const int N=107,K=133;
char c[N];
int f[N][N],t[N];
ull g[N],p[N];
void init()
{
p[0]=1;
for(int i=1;i<=105;i++)
p[i]=p[i-1]*K;
}
void Get(char *s,int n)
{
for(int i=1;i<=n;i++)
g[i]=g[i-1]*K+s[i];
}
int gethash(int l,int r)
{return g[r]-g[l-1]*p[r-l+1];}
main()
{
scanf("%s",c+1);
int n=strlen(c+1);
init();Get(c,n);
memset(f,63,sizeof f);
for(int i=1;i<=9;i++)t[i]=1;
for(int i=10;i<=99;i++)t[i]=2;
t[100]=3;
for(int i=1;i<=n;i++)f[i][i]=1;
for(int len=2;len<=n;len++)
for(int i=1;i<=n-len+1;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
for(int k=i;k<j;k++)
{
int l=k-i+1;
if(len%l!=0)continue;
if(gethash(i,j-l)==gethash(i+l,j))
f[i][j]=min(f[i][j],f[i][k]+2+t[len/l]);
}
}
cout<<f[1][n];
return 0;
}