dp……
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<string> using namespace std; int n; char s[105]; int dp[105][105]; bool lcr(int l,int r,int c) { int i,j,k; for(i=0;i<=c-1;i++) for(j=l+i;j<=r-c;j+=c) if(s[j]!=s[j+c])return false; return true; } int bao(int x) { if(x<10)return 1; if(x<100)return 2; return 3; } int main() { int i,j,k,l,t; scanf("%s",s+1); n=strlen(s+1); dp[n][n]=1; for(i=n-1;i>=1;i--){ dp[i][i]=1; for(j=i+1;j<=n;j++){ dp[i][j]=j-i+1; for(l=i;l<j;l++)dp[i][j]=min(dp[i][l]+dp[l+1][j],dp[i][j]); t=j-i+1; for(l=1;l<=t/2;l++) if(t%l==0&&lcr(i,j,l)) dp[i][j]=min(dp[i][j],dp[i][i+l-1]+2+bao(t/l)); } } printf("%d",dp[1][n]); return 0; }