题目链接：
一个简单的区间(DP)
设(f_{[l][r]})表示子串(lsim r)的最小长度，那么显然的有以下转移：
[f_{[l][r]}=r-l+1
]
什么都不做，长度不变。
[f_{[l][r]}=min_{i=l}^{r-1}limits{f_{[l][i]}+f_{[i+1][r]}}
]
枚举端点，由两个子串拼接而成。
[f_{[l][r]}=Length(c)+2+f_{[l][l+c-1]}
]
其中(Length(x))表示(x)的位数，(c)表示区间(lsim r)内的最短循环节。(2)表示两个括号。
(c)怎么求？暴力即可。
应该有更快的方法，字符串算法瞎搞搞
时间复杂度？(O(n^3log_2n))？（不太会算）
#include <cstdio>
#include <cstring>
inline int Min(int a,int b){return a<b?a:b;}
int f[105][105];
char s[105];
inline int Length(int x)//x的位数
{
return x>9?Length(x/10)+1:1;
}
inline bool Equal(int a,int b,int l)//判断以a,b为左端的两个长度为l的字符串是否相等
{
for(int i=1;i<=l;++i,++a,++b)
if(s[a]!=s[b])return false;
return true;
}
inline int MinFor(int l,int r)//求[l,r]的最小循环节
{
for(int i=1;i<=(r-l+1);++i)
if((r-l+1)%i==0)//枚举因子
{
bool Flag=true;
for(int j=l;j+i<=r;j+=i)
if(!Equal(j,j+i,i))
Flag=false,j=r;
if(Flag)return i;
}
return 0;
}
int DP(int l,int r)
{
if(l>r)return 0;//递归边界
if(f[l][r])return f[l][r];
f[l][r]=r-l+1;
int Fors=MinFor(l,r);
f[l][r]=Min(f[l][r],Length((r-l+1)/Fors)+2+DP(l,l+Fors-1));
for(int i=l;i<r;++i)
f[l][r]=Min(f[l][r],DP(l,i)+DP(i+1,r));
return f[l][r];
}
int main()
{
scanf("%s",s+1);
printf("%d
",DP(1,strlen(s+1)));
return 0;
}