欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【转】cf 825F - 19 String Compression 【kmp+dp】

程序员文章站 2024-03-14 13:54:58
...


@bin_gege


点击打开链接


题意:

             给你一个长度为8000的字符串,让你压缩,输出压缩后的长度,

             例如 ababcababc 压缩后 ab2c1ab2c1. 长度为10

              aaaaaaaaaa 压缩后 a10                  len=3


题解:

            我是觉得字符串处理最小循环节是不好弄的,想用kmp又不会用,后来看了 @bin_gege 的blog 才知道kmp能这样用,

            看来我还是对kmp理解太浅薄,,,

            n^2的dp   每次更新压缩后长度为i的最小长度,


           抄袭来的代码如下:

#include<bits/stdc++.h>

using namespace std;

void kmp_pre(char *x,int m,int *nxt){
    int i,j;
    j=nxt[0]=-1,i=0;
    while(i<m){
        while(-1!=j&&x[i]!=x[j])j=nxt[j];
        nxt[++i]=++j;
    }
}
const int N=10000;
int len,nxt[N],dp[N],cnt[N];
char s[N],buf[20],str[N];

int main(){
    scanf("%s",s);
    len=strlen(s);
    int t=1,q=10;
    for(int i=1;i<=len;++i) {
        if(i%q==0) t++,q*=10;
        cnt[i]=t;
        dp[i]=i+1;
    }
    for(int i=0;i<=len-1;++i){
        strcpy(str,s+i);
        kmp_pre(str,len-i,nxt);
        for(int j=1;i+j<=len;j++){//枚举长度
            int L=j-nxt[j];//以j结尾的子串的最小循环节
            if(j%L==0){//如果这个子串的长度恰好能整除最小循环节,那么可以按照最小循环节压缩。
                dp[i+j]=min(dp[i+j],dp[i]+L+cnt[j/L]);
            }else dp[i+j]=min(dp[i+j],dp[i]+j+1);
        }
    }
    printf("%d\n",dp[len]);
    return 0;
}