[USACO12JAN]视频游戏的连击Video Game Combos「建议收藏」

很早之前就做过啦补一下题解F(i,j)前i个的字符为j的匹配注意end要累加#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<queue>usingnam…

大家好,又见面了,我是你们的朋友全栈君。

[USACO12JAN]视频游戏的连击Video Game Combos「建议收藏」

 

很早之前就做过啦

补一下题解

F(i,j)前i个的字符为j的匹配

注意end要累加

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+100;
int n,m;
struct AC_AUTO{
    struct Node{
        int vis[26];
        int fail;
        int end;
    }AC[N];
    int cnt;
    inline void Clear(int p){
        memset(AC[p].vis,0,sizeof(AC[p].vis));
        AC[p].end=0;
        AC[p].fail=0;
    }
    inline void Build(string S){
        int R=S.length();
        int now=0;
        for(int i=0;i<R;i++){
            if(!AC[now].vis[S[i]-'A']){
                cnt++;
                Clear(cnt);
                AC[now].vis[S[i]-'A']=cnt;
            }
            now=AC[now].vis[S[i]-'A'];
        }
        AC[now].end++;
    }
    inline void Get_Fail(){
        queue<int> Q;
        for(int i=0;i<3;i++){
            if(AC[0].vis[i]){
                AC[AC[0].vis[i]].fail=0;
                Q.push(AC[0].vis[i]);
            }
        }
        while(!Q.empty()){
            int x=Q.front();
//			cout<<x<<" ";
            Q.pop();
            for(int i=0;i<3;i++){
                if(AC[x].vis[i]){
                    AC[AC[x].vis[i]].fail=AC[AC[x].fail].vis[i];	
                    Q.push(AC[x].vis[i]);
                }
                else AC[x].vis[i]=AC[AC[x].fail].vis[i];
            }
            AC[x].end+=AC[AC[x].fail].end;
//			cout<<AC[x].end<<'\n';
        }
    }
    int f[1001][1001];
    inline void DP(){
        int ans=0;
        memset(f,-1,sizeof(f));
        f[0][0]=0;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=cnt;j++){
                if(f[i-1][j]==-1)continue;
                for(int k=0;k<3;k++){
                    f[i][AC[j].vis[k]]=max(f[i][AC[j].vis[k]],f[i-1][j]+AC[AC[j].vis[k]].end);
                }
            }
        }
        for(int i=0;i<=cnt;i++){
            ans=max(ans,f[m][i]);
        }
        cout<<ans;
    }
}ACM;
int main(){
//	freopen("3119.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        ACM.Build(s);
    }
    ACM.Get_Fail();
    ACM.DP();
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/127721.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号