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

时间：2022-07-25 20:14:19

题面

sol

设\(f_{i,j}\)表示填了前\(i\)个字母，在\(AC\)自动机上跑到了节点\(j\)的最大得分。因为匹配需要暴跳\(fail\)所以预先把\(fail\)指针上面的匹配数传下来，这样就只要计算当前节点的贡献就可以了。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int N = 1005;

int n,k,tot,ch[3][N],fail[N],cnt[N],dp[N][N],ans;

char s[N];

queue<int>Q;

void Insert()

{

    scanf("%s",s);int l=strlen(s);

    int x=0;

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

    {

        if (!ch[s[i]-'A'][x]) ch[s[i]-'A'][x]=++tot;

        x=ch[s[i]-'A'][x];

    }

    cnt[x]++;

}

void Get_Fail()

{

    for (int i=0;i<3;i++) if (ch[i][0]) Q.push(ch[i][0]);

    while (!Q.empty())

    {

        int u=Q.front();Q.pop();

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

            if (ch[i][u]) fail[ch[i][u]]=ch[i][fail[u]],Q.push(ch[i][u]);

            else ch[i][u]=ch[i][fail[u]];

        cnt[u]+=cnt[fail[u]];

    }

}

void DP()

{

    memset(dp,-127,sizeof(dp));dp[0][0]=0;

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

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

            for (int l=0;l<3;l++)

                dp[i][ch[l][j]]=max(dp[i][ch[l][j]],dp[i-1][j]+cnt[ch[l][j]]);

}

int main()

{

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

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

    Get_Fail();

    DP();

    ans=dp[k][0];

    for (int i=1;i<=tot;i++) ans=max(ans,dp[k][i]);

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

    return 0;

}

相关文章