题解：SP10502 VIDEO - Video game combos

cff_0102 · 2024-09-26 15:02:53 · 题解

解法：AC 自动机 + dp。

首先先把 AC 自动机建出来，接着进行 dp。设 dp_{i,j} 表示输入 i 个字符，输入完最后一个字符后停在自动机的 j 点时最多获得几分。转移就枚举下一步输入的字母，并且对应看输入下一个字母后会多出几个能加分的后缀子串，加上相应的得分即可。最后的答案就是所有 dp_{k,i} 取最大值。

注意 dp 数组的初始化。

#include<bits/stdc++.h>
using namespace std;
const int N=309,K=1010;
int tr[N][3],cnt=0,pre[N],ed[N];
void ins(string s){
    int nw=0;
    for(int i=0;i<s.length();i++){
        int c=s[i]-'A';
        if(tr[nw][c]==0)tr[nw][c]=++cnt;
        nw=tr[nw][c];
    }
    ed[nw]++;
}
void build(){
    queue<int>q;
    for(int i=0;i<3;i++)if(tr[0][i])q.push(tr[0][i]);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int y=0;y<3;y++){
            if(tr[x][y]==0)tr[x][y]=tr[pre[x]][y];
            else{
                pre[tr[x][y]]=tr[pre[x]][y];
                q.push(tr[x][y]);
            }
        }
        ed[x]+=ed[pre[x]];//记得加上沿着 fail 边往上跳能跳到多少个字符串的末尾
    }
}
int dp[K][N];//输入 i 个字符，最后停在 AC 自动机的点 j 时能获得几分
void solve(int kk){
    for(int i=0;i<=kk;i++)dp[i][0]=0;
    for(int i=0;i<kk;i++){
        for(int j=0;j<=cnt;j++){
            for(int k=0;k<3;k++){//接下来往哪走呢 
                dp[i+1][tr[j][k]]=max(dp[i+1][tr[j][k]],dp[i][j]+ed[tr[j][k]]);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        ins(s);
    }
    build();
    memset(dp,-0x3f,sizeof(dp));
    solve(k);
    int ans=0;
    for(int i=0;i<=cnt;i++){
//      cout<<dp[k][i]<<" ";
        ans=max(ans,dp[k][i]);
    }
    cout<<ans;
    return 0;
}

AC 记录：https://www.luogu.com.cn/record/178447532。