bzoj 1090: [SCOI2003]字符串折叠

/**************************************************************
    Problem: 1090
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:32 ms
    Memory:1376 kb
****************************************************************/
 
/*
    第一个折叠仿佛没有什么卵用？？ 更大了、、、
    然后就是区间DP 缩短长度 
*/
#include<bits/stdc++.h>
using namespace std;
const int N=150;
char s[N];
int n,f[N][N];
bool check(int cl,int cr,int l,int r) // cl cr重复可得到 l r 
{
    if((r-l+1)%(cr-cl+1)!=0) return 0;
    for(int i=l;i<=r;i++) 
        if(s[i]!=s[(i-l)%(cr-cl+1)+cl]) return 0; 
    return 1;
}
int calc(int x) {int res=0; while(x) res++,x/=10; return res;} 
int main()
{
    scanf("%s",s+1); n=strlen(s+1);
    for(int i=1;i<=n;i++) f[i][i]=1;
    for(int len=2;len<=n;len++)
    for(int i=1;i<=n-len+1;i++)
    {
        int j=i+len-1;
        f[i][j]=len;
        for(int k=i;k<j;k++)
        {
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            if(check(i,k,k+1,j)) // i,k 重复可得到 k+1,j  
                f[i][j]=min(f[i][j],f[i][k]+2+calc((j-k)/(k-i+1)+1));
                // +1是为了方便计算他是几位数 
        }
    }
    printf("%d\n",f[1][n]);
     
    return 0;
}