bzoj 1090: [SCOI2003]字符串折叠

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 int ma[105][105],f[105][105];
 6 char ch[106];
 7 bool pan(int l,int r,int l1,int r1)
 8 {
 9     if((r-l+1)%(r1-l1+1)!=0)
10       return 0;
11     for(int i=l;i<=r;i++)
12       if(ch[i]!=ch[l1+(i-l)%(r1-l1+1)])
13         return 0;
14     return 1;
15 }
16 int suan(int a1)
17 {
18     int sum=0;
19     for(;a1;)
20       {
21         sum++;
22         a1/=10;
23       }
24     return sum;
25 }
26 int dp(int l,int r)
27 {
28     int sum=r-l+1;
29     if(sum==1)
30       return 1;
31     if(ma[l][r])
32       return f[l][r];
33     for(int i=l;i<r;i++)
34       {
35         sum=min(sum,dp(l,i)+dp(i+1,r));
36         if(pan(i+1,r,l,i))
37           sum=min(sum,dp(l,i)+2+suan((r-i)/(i-l+1)+1));
38       }
39     ma[l][r]=1;
40     f[l][r]=sum;
41     return sum;
42 }
43 int main()
44 {
45     scanf("%s",ch+1);
46     printf("%d",dp(1,strlen(ch+1)));
47     return 0;
48 }