[bzoj1090]字符串折叠

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mod 998244353
 4 int n,sum[105],mi[105],f[105][105];
 5 char s[105];
 6 int calc(int k){
 7     int s=0;
 8     while (k){
 9         s++;
10         k/=10;
11     }
12     return s;
13 }
14 int hash(int l,int r){
15     return (sum[r]-1LL*sum[l-1]*mi[r-l+1]%mod+mod)%mod;
16 }
17 int dp(int l,int r){
18     if (f[l][r])return f[l][r];
19     int ans=r-l+1;
20     for(int i=1;i<r-l+1;i++)
21         if ((r-l+1)%i==0){
22             int h=hash(l,l+i-1),flag=0;
23             for(int j=1;j<(r-l+1)/i;j++)
24                 if (h!=hash(l+j*i,l+j*i+i-1))flag=1;
25             if (!flag)ans=min(ans,calc((r-l+1)/i)+dp(l,l+i-1)+2);
26         }
27     for(int k=l;k<r;k++)ans=min(ans,dp(l,k)+dp(k+1,r));
28     return f[l][r]=ans;
29 }
30 int main(){
31     scanf("%s",s);
32     n=strlen(s);
33     mi[0]=1;
34     for(int i=1;i<n;i++)mi[i]=mi[i-1]*31LL%mod;
35     sum[0]=s[0]-‘A‘+1;
36     for(int i=1;i<n;i++)sum[i]=(sum[i-1]*31LL+s[i]-‘A‘+1)%mod;
37     printf("%d",dp(0,n-1));
38 }