题目
题解
用$f_{i,j}$表示区间$[i,j]$压缩后的最小长度，直接暴力枚举是否可以压缩即可，子串是否相同用$Hash$判断即可
复杂度跑不满的$O(n^4)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int N=105,Base=233,mod=1e9+7;
int n;
int H[N],qwq[N];
int f[N][N];
char a[N];
int Hash(int l,int r) {return (H[r]-1ll*H[l-1]*qwq[r-l+1]%mod+mod)%mod;}
int GET_NUM(int x)
{
int num=0;
while(x) ++num,x/=10;
return num;
}
bool look(int x,int l,int r)
{
int o=Hash(l,l+x-1);
for(int i=l+x;i<=r;i+=x)
if(Hash(i,i+x-1)!=o) return 0;
return 1;
}
int main()
{
scanf("%s",a+1),n=strlen(a+1),qwq[0]=1;
memset(f,1,sizeof(f));
for(int i=1;i<=n;++i)
qwq[i]=1ll*qwq[i-1]*Base%mod,H[i]=(1ll*H[i-1]*Base%mod+a[i])%mod,f[i][i]=1;
for(int i=2;i<=n;++i)
for(int l=1,r;l<=n-i+1;++l)
{
r=l+i-1;
for(int j=l;j<r;++j)
f[l][r]=min(f[l][r],f[l][j]+f[j+1][r]);
for(int j=1;j<=i;++j)
if(i%j==0&&look(j,l,r))
f[l][r]=min(f[l][r],f[l][l+j-1]+2+GET_NUM(i/j));
}
return printf("%d",f[1][n]),0;
}
