[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)


相关推荐

  • 计算机网络——DHCP协议详解

    计算机网络——DHCP协议详解由浅入深理解DHCP协议

  • pycharm 换行_pycharm回车不能换行

    pycharm 换行_pycharm回车不能换行python脚本有时一行代码写的非常长,一个屏幕塞不下,左右拉动滚动条视觉不友好。第一种方法:python里有换行标识”\”,如jfdb=spark.read.format(“jdbc”).option(“driver”,mysql_driver).option(“url”,mysql_url).option(“dbtable”,”xxxxxxxxxxxxxxxxxxxxxxxx”).option(“user”,mysql_acount).option(“password”,mysql_pa

  • 复合主键与联合主键[通俗易懂]

    复合主键与联合主键[通俗易懂]一、复合主键 所谓的复合主键就是指你表的主键含有一个以上的字段组成,不使用无业务含义的自增id作为主键。比如 createtabletest(namevarchar(19),idnumber,valuevarchar(10),primarykey(name,id))上面的name和id字段组合起来就是你

  • 【Custom Mutator Fuzz】AFL++自定义突变API「建议收藏」

    【Custom Mutator Fuzz】AFL++自定义突变API「建议收藏」前言其实这篇是临时加进来的,因为下一篇文章是libprotobuf+AFL++的内容,所以写的时候需要使用AFL++自定义突变的API,觉得还是需要单独写一篇API的介绍,一共十一个方法,也不是很多,下一篇文章就不再用大篇幅描述API了~编写不易,如果能够帮助到你,希望能够点赞收藏加关注哦Thanks♪(・ω・)ノPS:文章末尾有联系方式,交个朋友吧~本文链接:模糊测试系列往期回顾:【CustomMutatorFuzz】Libprotobuf+LibFuzzerCustomM.

  • JS算法题 JavaScript常见算法题 基础语法案例(持续更新)2022年3月30日

    JS算法题 JavaScript常见算法题 基础语法案例(持续更新)2022年3月30日JavaScript基础案例,用法,算法题

  • 补码运算中的溢出_二进制补码运算溢出判断

    补码运算中的溢出_二进制补码运算溢出判断当两个以补码表示的负数相加时,会遇到两个问题。第一是两个负数的符号位相加,1+1后,本位为零,似乎负数相加变成了正数;其二是两个负数的数值部分之和,如果不向符号位进位,是不是就说明运算结果没有溢出?但不进位最终将导致两个负数相加成了正数,显然是错误的,这该怎么解释?如果两个以补码表示的负数的数值部分之和向符号位进位,会使运算结果依然为负数,那么这个运算结果是正确的吗?下面我们分析一下这个问题:

发表回复

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

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