原題地址本沙茶在2009年1月曾經(jīng)在
RQNOJ上捉過這題，那時(shí)候是很難的題，現(xiàn)在就很水了囧……（當(dāng)然，本沙茶那個(gè)時(shí)候不會(huì)exKMP，是用暴力的，可是時(shí)間復(fù)雜度仍能是O(N
3)）。
F[i][j]=min{F[i][k]+F[k+1][j]，min{((j-i+1)/(k-i+1)的十進(jìn)制位數(shù))+2+F[i][k]，
k-i+1}, i<=k<j，第二項(xiàng)需要滿足原字符串[i..j]這一段恰好由[i..k]這一段的若干次復(fù)制得到}
（加上k-i+1是因?yàn)閷τ谝韵氯N重疊字符串，不壓縮比壓縮要短：AA型、AAA型、ABAB型）
邊界：F[i][i]=1；
問題是在上述方程的第二項(xiàng)里如何求出可行的k。顯然，只需要對[i..j]這一段作exKMP，求出nx，然后k可行當(dāng)且僅當(dāng)滿足：（1）nx[k+1]=j-k；（2）(k-i+1)|(j-i+1)；
不過，本題在寫exKMP的過程中會(huì)出現(xiàn)很囧的問題……由于下標(biāo)不是從0開始，而是從i開始，所以很多地方關(guān)于下標(biāo)的計(jì)算都要改掉，非常不方便，而且很容易疵掉。與其這樣，還不如把[i..j]這一段復(fù)制到一個(gè)新字符串里，下標(biāo)從0開始。對于其它的某些字符串算法和數(shù)據(jù)結(jié)構(gòu)，或許也是這樣囧……
代碼：
#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;
}