首页 > 代码库 > Educational Codeforces Round 25 F. String Compression(kmp+dp)
Educational Codeforces Round 25 F. String Compression(kmp+dp)
题目链接:Educational Codeforces Round 25 F. String Compression
题意:
给你一个字符串,让你压缩,问压缩后最小的长度是多少。
压缩的形式为x(...)x(...) x表示(...)这个出现的次数。
题解:
考虑dp[i]表示前i个字符压缩后的最小长度。
转移方程解释看代码,这里要用到kmp来找最小的循环节。
当然还有一种找循环节的方式就是预处理lcp,然后通过枚举循环节的方式。
这里我用的kmp找的循环节。复杂度严格n2。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 void kmp_pre(char *x,int m,int *nxt){ 6 int i,j; 7 j=nxt[0]=-1,i=0; 8 while(i<m){ 9 while(-1!=j&&x[i]!=x[j])j=nxt[j]; 10 nxt[++i]=++j; 11 } 12 } 13 const int N=10000; 14 int len,nxt[N],dp[N],cnt[N]; 15 char s[N],buf[20],str[N]; 16 17 int main(){ 18 scanf("%s",s); 19 len=strlen(s); 20 F(i,1,len)cnt[i]=sprintf(buf,"%d",i),dp[i]=i+1; 21 F(i,0,len-1) 22 { 23 strcpy(str,s+i); 24 kmp_pre(str,len-i,nxt); 25 for(int j=1;i+j<=len;j++)//枚举长度 26 { 27 int L=j-nxt[j];//以j结尾的子串的最小循环节 28 if(j%L==0)//如果这个子串的长度恰好能整除最小循环节,那么可以按照最小循环节压缩。 29 { 30 dp[i+j]=min(dp[i+j],dp[i]+L+cnt[j/L]); 31 }else dp[i+j]=min(dp[i+j],dp[i]+j+cnt[1]); 32 } 33 } 34 printf("%d\n",dp[len]); 35 return 0; 36 }
Educational Codeforces Round 25 F. String Compression(kmp+dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。