洛谷 4302 BZOJ 1090 SCOI2003 字符串折叠

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define LL long long
 5 #define rg register
 6 #define N 200
 7 using namespace std;
 8 int n,m,f[N][N];
 9 char s[N];
10 inline int read(){
11     int k=0,f=1; char c=getchar();
12     while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
13     while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
14     return k*f;
15 }
16 inline bool check(int l,int r,int end){
17     int l1=r-l+1,l2=end-l+1;
18     if(l2%l1) return 0;
19     m=l2/l1;
20     for(rg int i=1;i<=m;i++){
21         int st=l+(i-1)*l1;
22         for(rg int j=0;j<l1;j++) if(s[l+j]!=s[st+j]) return 0;
23     }
24     return 1;
25 }
26 inline int qlen(int x){
27     int cnt=0;
28     while(x){
29         x/=10;
30         cnt++;
31     }
32     return cnt;
33 }
34 int main(){
35     scanf("%s",s+1); n=strlen(s+1);
36     for(rg int i=0;i<=n;i++)
37         for(rg int j=i;j<=n;j++) f[i][j]=j-i+1;
38     for(rg int l=0;l<=n;l++){
39         for(rg int i=1;i+l-1<=n;i++){
40             int j=i+l-1;
41             for(rg int k=i;k<=j;k++){
42                 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
43                 if(check(i,k,j)){
44                     f[i][j]=min(f[i][j],f[i][k]+2+qlen(m));
45 //                  printf("%d %d %d\n",i,k,j);
46                 }
47             }
48         }
49     }
50     printf("%d\n",f[1][n]);
51     return 0;
52 }