P3041 [USACO12JAN]视频游戏的连击Video Game Combos

思路

简单的AC自动机上dp，暴力跳fail向子节点直接转移即可

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

using namespace std;

int trie[400][3],Nodecnt,mark[400],fail[400],dp[1001][400],root,k,n;

char t[400];

void insert(char *s,int len){

    int o=root;

    for(int i=1;i<=len;i++){

        if(!trie[o][s[i]-'A'])

            trie[o][s[i]-'A']=++Nodecnt;

        o=trie[o][s[i]-'A'];

    }

    mark[o]++;

}

void build_AC(void){

    queue<int> q;

    for(int i=0;i<3;i++){

        if(trie[root][i]){

            fail[trie[root][i]]=root;

            q.push(trie[root][i]);

        }

    }

    while(!q.empty()){

        int x=q.front();

        q.pop();

        for(int i=0;i<3;i++){

            if(trie[x][i]){

                fail[trie[x][i]]=trie[fail[x]][i];

                q.push(trie[x][i]);

            }

            else{

                trie[x][i]=trie[fail[x]][i];

            }

        }

    }

}

int query(void){

    int ans=0;

    int o=root;

    for(int i=0;i<=k;i++)

        for(int j=0;j<=Nodecnt;j++)

            dp[i][j]=-0x3f3f3f3f;

    dp[0][o]=0;

    for(int i=0;i<k;i++)

        for(int j=0;j<=Nodecnt;j++){

            for(int k=0;k<3;k++){

                int p=trie[j][k],mid=0;

                for(;p;p=fail[p])

                    mid+=mark[p];

                dp[i+1][trie[j][k]]=max(dp[i+1][trie[j][k]],dp[i][j]+mid);

                ans=max(ans,dp[i+1][trie[j][k]]);

            }

        }

    return ans;

}

int main(){

    scanf("%d %d",&n,&k);

    for(int i=1;i<=n;i++){

        scanf("%s",t+1);

        int lent=strlen(t+1);

        insert(t,lent);

    }

    build_AC();

    printf("%d\n",query());

    return 0;

}

巴特西

P3041 [USACO12JAN]视频游戏的连击Video Game Combos

思路

代码

最新文章

热门文章