Codeforces 825F String Compression DP(最小循环节)
程序员文章站
2024-03-14 13:59:28
...
题意:字符串s,s能压缩成c1s1c2s2..cksk时,表示把s1写c1次,s2写c2次...能得到s
|s|<=8000,问s能压缩后最小长度为?
设dp[i] 前缀i压缩后的最小长度
dp[i]=min(dp[i],dp[j]+"s[j+1]..s[i]") 最后一段肯定用最小循环节来表示
|s|<=8000,问s能压缩后最小长度为?
设dp[i] 前缀i压缩后的最小长度
dp[i]=min(dp[i],dp[j]+"s[j+1]..s[i]") 最后一段肯定用最小循环节来表示
求出后缀i的next数组时,就能知道i-j(j>=i)最小循环节的长度 O(n^2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const int inf=0x3f3f3f3f;
const int N=8e3+20;
char s[N];
int f[N];
void getfail(char s[],int fail[],int n)
{
fail[1]=0;
for(int i=1;i<n;i++)
{
int p=fail[i];
while(p&&s[p+1]!=s[i+1])
p=fail[p];
fail[i+1]=p+(s[p+1]==s[i+1]);
}
}
int calc(int x)
{
int res=0;
while(x) res++,x/=10;
return res;
}
int dp[N];
int main()
{
while(scanf("%s",s+1)!=EOF)
{
int n=strlen(s+1);
memset(dp,inf,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++)
{
getfail(s+i-1,f,n-i+1);
for(int j=i;j<=n;j++)
{
int len=j-i+1,x=len-f[len],num;
if(len%x==0)
num=len/x;
else
num=1;
dp[j]=min(dp[j],dp[i-1]+len/num+calc(num));
}
}
cout<<dp[n]<<endl;
}
return 0;
}