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
",query());
    return 0;
}