思路
容易想到是个动态规划。首先设 \(f_i\) 表示字符串前 \(i\) 个字符所组成的字符串的答案。状态定义好了,接下来就是考虑如何转移了。因为由 \(f_i\) 可以得到所有 \(f_j\),其中 \(i+j\le len\),转移方程为 \(f_i=f_j+x\),其中 \(x\) 为 字符串 \(i+1\) 至 \(j\) 的最优压缩。
接下来只要把如何求最优压缩解决了这道题就做出来了。考虑暴力求解,随便选择一个前缀 \(T\) 遍历整个字符串,看 \(T\) 是否是原字符串的循环串。如何优化呢?我们要做的事情就是找一个最长前缀 \(T\),使得字符串 \(T\) 是原字符串的循环串。有没有感觉似曾相识?对了,就是对字符串求一遍 KMP 的 border 数组。
所以转移方程就出来了 $f_{i + k} = \min(f_{i + k}, f_i + (k - nxt_k) + sum) $。
这道题也就做出来了,具体参见代码。
代码
#include <bits/stdc++.h>
using namespace std;
int f[100010];
int nxt[8010];
char s[8010], t[8010];
void kmp(char t[])
{
memset(nxt, 0, sizeof(nxt));
int j = 0;
nxt[1] = 0, nxt[0] = 0;
int len = strlen(t + 1);
for (int i = 2; i <= len; i++)
{
while (j && t[i] != t[j + 1])
j = nxt[j];
if (t[i] == t[j + 1])
j++;
nxt[i] = j;
}
}
int main()
{
cin >> s + 1;
int len = strlen(s + 1);
for (int i = 1; i <= len; i++)
f[i] = i + 1;
for (int i = 0; i < len; i++)
{
memset(t, 0, sizeof(t));
int ss = 0;
for (int j = i + 1; j <= len; j++)
{
t[++ss] = s[j];
}
kmp(t);
for (int k = 1; k + i <= len; k++)
{
if (k % (k - nxt[k]) == 0)
{
int cnt = k / (k - nxt[k]), sum = 0;
while (cnt)
sum++, cnt /= 10;
f[i + k] = min(f[i + k], f[i] + (k - nxt[k]) + sum);
}
else
f[i + k] = min(f[i + k], f[i] + 1 + k);
}
}
cout << f[len];
return 0;
}
标签:nxt,String,int,题解,len,CF825F,字符串,8010
From: https://www.cnblogs.com/merlinkkk/p/18306124