我居然在第一个最优解？
设(f_{i,j})为([i,j])中的最短长度。
得
[f_{i,j} = min(min limits_{i le k < j} {f_{i,k} + f_{k + 1,j}},min limits_{i le k < j \ s[i,k]是s[i,j]的循环节} {f_{i,k} + LEN(L) + 2})
]
其中(LEN(x))为(x)的位数，(L)为循环节数。
时间复杂度(O(n ^ 4))?显然不是。
在(s[i,k])的长度不整除(s[i,j])的长度时，显然不成立，剪枝。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 110;
char s[N];
int f[N][N];
int n;
int check(int l, int r, int R)
{
int k = l;
int cnt = 0;
for (int i = l; i <= R; i++)
{
if (k > r)
k = l, cnt++;
if (s[k] != s[i])
return 0;
++k;
}
return cnt;
}
int Getlen(int x)
{
int cnt = 0;
while (x)
{
cnt++;
x /= 10;
}
return cnt;
}
int main(void)
{
scanf("%s", s + 1);
n = strlen(s + 1);
// printf("%d
", n);
// for (int i = 1; i <= n; i++)
// {
// cout << s[i];
// }
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
f[i][j] = (i == j) ? 1 : inf;
}
}
// printf("n = %d
", n);
for (int len = 2; len <= n; len++)
{
for (int i = 1, j = i + len - 1; i <= n - len + 1; i++, j++)
{
// printf("i = %d,j = %d,%d
", i, j, i <= n);
for (int k = i; k < j; k++)
{
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
}
for (int k = i; k < j; k++)
{
int L = (k - i + 1);
if (len % L != 0)
continue;
int ck = check(i, k, j);
// printf("check(%d,%d,%d) = %d
", i, k, j, ck);
if (ck > 0)
{
f[i][j] = min(f[i][j], f[i][k] + Getlen(len / L) + 2);
}
}
}
}
printf("%d
", f[1][n]);
return 0;
}