Codeforces Round #543 (Div. 2) F dp + 二分 + 字符串哈希

https://codeforces.com/contest/1121/problem/F

题意

给你一个有n(<=5000)个字符的串，有两种压缩字符的方法：
1. 压缩单一字符，代价为a
2. 压缩一个串，条件是这个串是前面整个串的连续子串，代价为b

题解

• n<=5000
• 定义dp[i]为压缩前i个字符的代价，则答案为dp[n]
• dp[i]=min(dp[i-1]+a,min(dp[j]+b)(即[j+1,i]为[1,j]的子串))
• 用字符串哈希处理判定一个串是否为前面的子串

坑点

• 串abab，如何判定后面一个ab是前面ab的子串？
  • 照旧给每一个位置加权

  • 判定的时候，首先将权值加到同一个权级再比较

    比如存在一个首字符在i和一个首字符在j的串，那么比较的时候哈希值分别都要乘以(size-i)和(size-j)，得到权级都是size的串

• 两层for已经是n*n复杂度，还需要判定后面的串是否是前面串的子串？
  • 一开始想法就是用一个map[i]记录每个位置之前哈希值的出现次数，但是会超内存
  • 换一个\(n*n*log(n)\)的算法，二分找出最小的位置\(log(n)\)，枚举前面每一个位置固定长度串\(n\)

代码

#include<bits/stdc++.h>
#define P 47               //加权的质数较小
#define mod 1000000003     //哈希表的质数较大
#define ll long long 
using namespace std;
int n,a,b,i,j,sum[5005],dp[5005],pw[6000],l,mid,r;
char s[5005];

void init(){
    pw[0]=1;
    for(int i=1;i<=n+100;i++)
        pw[i]=(ll)pw[i-1]*P%mod;
    for(int i=1;i<=n;i++)
        sum[i]=(sum[i-1]+(ll)pw[i]*(s[i]-'a'+1)%mod)%mod;
}

int geths(int i,int j){
    return (int)(((ll)sum[j]-sum[i-1]+mod)%mod*pw[n+50-i]%mod);
}

int ck(int p,int i,int j,int len){
    int hs=geths(i,j);
    for(int k=1;k<=p-len+1;k++){
        if(geths(k,k+len-1)==hs)return 1;
    }
    return 0;
}

int main(){
    cin>>n>>a>>b;
    scanf("%s",s+1);
    init(); 
    dp[0]=0;
    for(i=1;i<=n;i++){
        dp[i]=dp[i-1]+a;
        l=1;r=i-1;
        while(l<r){
            mid=(l+r)/2;
            if(ck(i-mid,i-mid+1,i,mid))l=mid+1;
            else r=mid;
        }
        while(!ck(i-l,i-l+1,i,l))l--;
        if(l>=1)dp[i]=min(dp[i-l]+b,dp[i]);
    }
    cout<<dp[n];
}

Codeforces Round #543 (Div. 2) F dp + 二分 + 字符串哈希

原文：https://www.cnblogs.com/VIrtu0s0/p/10487367.html