折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S  S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。 3. 如果A  A’, BB’，则AB  A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B)  AAACBB，而2(3(A)C)2(B)AAACAAACBB 给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

仅一行，即字符串S，长度保证不超过100。

仅一行，即最短的折叠长度。

NEERCYESYESYESNEERCYESYESYES

14

一个最短的折叠为：2(NEERC3(YES))

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #define N 107

 using namespace std;

 int len;

 int f[N][N],mark[N][N];

 char s[N];

 bool judge(int l,int r,int hl,int hr)

 {

     int mod=(r-l)+;

     if ((hr-hl+)%(r-l+)!=) return false;

     for (int i=;i<hr-hl+;i++)

         if (s[l+i%mod]!=s[hl+i]) return false;

     return true;

 }

 int wei(int x)

 {

     int zhi=;

     while (x)

     {

         zhi++;

         x/=;

     }

     return zhi;

 }

 int dfs(int l,int r)

 {

     if (l==r) return ;

     if (mark[l][r]) return f[l][r];

     mark[l][r]=;

     int res=r-l+;

     for (int i=l;i<r;i++)

     {

         res=min(res,dfs(l,i)+dfs(i+,r));

         if (judge(l,i,i+,r)) res=min(res,dfs(l,i)++wei((r-i)/(i-l+)+));

     }

     return f[l][r]=res;

 }

 int main()

 {

     scanf("%s",s);

     len=strlen(s);

     printf("%d\n",dfs(,len-));

 }