Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 110

char s[MAXL];

int n;

int f[MAXL][MAXL];

bool get(int l,int r,int len)

{

	if((r - l + 1) % len != 0)return false;

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

	{

		if(s[i] != s[i - len])return false;

	}

	return true;

}

int cnt(int k)

{

	int res = 0;

	while(k > 0)

	{

		++res;

		k /= 10;

	}

	return res;

}

int main()

{

	scanf("%s",s + 1);

	n = strlen(s + 1);

	memset(f,0x3f,sizeof(f));

	for(int i = 1;i <= n;++i)f[i][i] = 1;

	for(int l = 2;l <= n;++l)

	{

		for(int i = 1;i <= n - l + 1;++i)

		{

			int j = i + l - 1;

			for(int k = i;k < j;++k)

			{

				f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j]);

				if(get(i,j,k - i + 1))f[i][j] = min(f[i][j],f[i][k] + cnt((j - i + 1) / (k - i + 1)) + 2);

			}

		}

	}

	cout << f[1][n] << endl;

	return 0;

}