原题地址本沙茶在2009年1月曾经在
RQNOJ上捉过这题，那时候是很难的题，现在就很水了囧……（当然，本沙茶那个时候不会exKMP，是用暴力的，可是时间复杂度仍能是O(N
3)）。
F[i][j]=min{F[i][k]+F[k+1][j]，min{((j-i+1)/(k-i+1)的十进制位数)+2+F[i][k]，
k-i+1}, i<=k<j，第二项需要满足原字符串[i..j]这一段恰好由[i..k]这一段的若干次复制得到}
（加上k-i+1是因为对于以下三种重叠字符串，不压缩比压缩要短：AA型、AAA型、ABAB型）
边界：F[i][i]=1；
问题是在上述方程的第二项里如何求出可行的k。显然，只需要对[i..j]这一段作exKMP，求出nx，然后k可行当且仅当满足：（1）nx[k+1]=j-k；（2）(k-i+1)|(j-i+1)；
不过，本题在写exKMP的过程中会出现很囧的问题……由于下标不是从0开始，而是从i开始，所以很多地方关于下标的计算都要改掉，非常不方便，而且很容易疵掉。与其这样，还不如把[i..j]这一段复制到一个新字符串里，下标从0开始。对于其它的某些字符串算法和数据结构，或许也是这样囧……
代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 110, INF = ~0U >> 2;
int n, F[MAXN][MAXN], nx[MAXN], res;
char ss[MAXN + 1], ss0[MAXN + 1];
void init()
{
scanf("%s", ss); n = strlen(ss);
}
int sol0(int l, int r)
{
int W = r - l + 1; re3(i, l, r) ss0[i - l] = ss[i];
nx[0] = W; nx[1] = nx[0] - 1; re(i, W) if (ss0[i] != ss0[i + 1]) {nx[1] = i; break;}
int k = 1, len, p = k + nx[k] - 1, x, y;
re2(i, 2, W) {
len = nx[i - k];
if (i + len <= p) nx[i] = len; else {
x = p + 1; y = p - i + 1; if (y < 0) {x++; y = 0;}
for (; x<=W && ss0[x]==ss0[y]; x++, y++) ;
nx[i] = y; k = i; p = i + y - 1;
}
}
int res0 = INF, tmp, V;
re2(i, 1, W) if (!(W % i) && nx[i] == W - i) {
V = F[l][l + i - 1] + 2; tmp = W / i; while (tmp) {tmp /= 10; V++;}
if (W < V) V = W;
if (V < res0) res0 = V;
}
return res0;
}
void solve()
{
re(i, n) F[i][i] = 1;
int j, tmp;
re2(x, 1, n) re(i, n-x) {
j = i + x; F[i][j] = sol0(i, j);
re2(k, i, j) {tmp = F[i][k] + F[k + 1][j]; if (tmp < F[i][j]) F[i][j] = tmp;}
}
res = F[0][n - 1];
}
void pri()
{
printf("%d\n", res);
}
int main()
{
init();
solve();
pri();
return 0;
}