【AC自动机+DP】USACO2012 JAN GOLD_Video Game Combos

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题目大意】

给你个模式串（每个长度≤15，1≤N≤20），串中只含有三种字母。求一长度为K（1≤K≤1000）的字符串，使得匹配数最大（重复匹配计多次），输出最大值。

【解题思路】

W老师给的题，然而我不会做。呜呜呜谢谢丁爷爷教我做题，神犇丁爷爷%%%。下面都是丁爷爷的话，和我没有关系。然而丁爷爷没有博客（也许是我不造？( •̀ ω •́ )y）现在正在码USACO给的标答…

COPYRIGHT@丁爷爷

代码是我自己的，因为是用指针写的会有点长，丁爷爷的代码只有60+。总之祝丁爷爷继续超神下去……

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define lnum 3

 using namespace std;

 const int MAXK=;

 const int MAXN=*+;

 int cnt=-;

 struct ACauto

 {

     int id;

     ACauto* next[lnum];

     ACauto* fail;

     ACauto()

     {

         id=++cnt;

         for (int i=;i<lnum;i++) next[i]=NULL;

         fail=NULL;

     }

 };

 ACauto* rt=new ACauto();

 int go[MAXN][lnum];//编号为i的节点的三个后继的编号，如果不存在则为0

 int combo[MAXN];//编号为i的节点及其后缀能够产生的最大匹配数

 int dp[MAXN][MAXK];//在编号为i的节点上再走j步能够达到的最大值

 int n,k;

 void insert(ACauto* rt,char* str)

 {

     int len=strlen(str);

     ACauto* now=rt;

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

     {

         int index=str[i]-'A';

         if (now->next[index]==NULL)

         {

             now->next[index]=new ACauto();

         }

         go[now->id][index]=now->next[index]->id;

         now=now->next[index];

     }

     combo[now->id]=;

     //在不包含后缀的情况下，当前结尾可以产生一个匹配

 }

 void buildfail(ACauto* rt)

 {

     queue<ACauto*> que;

     que.push(rt);

     while (!que.empty())

     {

         ACauto* head=que.front();que.pop();

         for (int i=;i<lnum;i++)

         {

             if (head->next[i]==NULL) continue;

             if (head==rt)

                 head->next[i]->fail=rt;

             else

             {

                 ACauto* tmp=head->fail;

                 while (tmp!=NULL)

                 {

                     if (tmp->next[i]!=NULL)

                     {

                         head->next[i]->fail=tmp->next[i];

                         break;

                     }

                     else

                     tmp=tmp->fail;

                 }

                 if (tmp==NULL) head->next[i]->fail=rt;

             }

             combo[head->next[i]->id]+=combo[head->next[i]->fail->id];

             //当前节点及其字符串后缀的节点均可能为模式串，故每次都要沿着指针计算这一步能够产生的新的匹配数。由于计算时累加的，只需沿fail指针走一步即可。

             que.push(head->next[i]);

         }

     }

 }

 void init()

 {

     memset(go,,sizeof(go));

     memset(combo,,sizeof(combo));

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

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

     {

         char str[];

         scanf("%s",str);

         insert(rt,str);

     }

     buildfail(rt);

 }

 void dp_process()

 {

     memset(dp,,sizeof(dp));

     for (int i=;i<=cnt;i++) dp[][i]=combo[i];

     int cur=;

     for (int l=;l<=k;l++)

     {

         cur^=;

         for (int i=;i<=cnt;i++)

         {

             dp[cur][i]=;

             for (int j=;j<lnum;j++)

                 dp[cur][i]=max(dp[cur][i],combo[i]+dp[cur^][go[i][j]]);

         }

     }

     printf("%d",dp[cur][]);

 }

 int main()

 {

     init();

     dp_process();

     return ;

 }