hdu 4057

http://acm.hdu.edu.cn/showproblem.php?pid=4057
私はそれをacオートマトン+dpと呼ぶのが好きではありません.個人的にはacオートマトン上のdpと呼ぶのがもっといいと思います.なぜなら、私たちがacオートマトンのノードの状態で状態と状態の間の移行を構築することにあります.なぜacオートマトンで状態を構築するのかというと、個人的にはテーマが与えた文字列のある移行の間の情報(正しいことを保証する)が含まれていると認識しています.しかも状態数が少ない(時間再検査が小さいことが保証されている)
dp[node][state]は現在の長さがnodeノードに達することを表し、state文字列(バイナリ状態で圧縮)を含む.

#include <cstdlib>
#include <iostream>
#include <algorithm> 

using namespace std;
const int maxn=1010;
int chd[maxn][4],fail[maxn],word[maxn],sz,sw[128];
bool dp1[1010][1050],dp2[1010][1050];
int n,len;
char s[110];
int val[20];

void Ins(char *a,int val)
{
     int p=0;
    for(;*a;a++)     
    {
        int id=sw[*a];                 
        if(!chd[p][id])
        {
             memset(chd[sz],0,sizeof(chd[sz]));               
             word[sz]=0;
             chd[p][id]=sz++;
        }
        p=chd[p][id];
    }
    word[p]|=(1<<val);
}
int Que[maxn];
void ac()
{
    int *s=Que,*e=Que; 
    for(int i=0;i<4;i++)     
      if(chd[0][i])
      {
          *e++=chd[0][i];
          fail[chd[0][i]]=0;
      }
    while(s!=e)  
    {
         int p=*s++;
         for(int i=0;i<4;i++)             
           if(chd[p][i])
           {
                *e++=chd[p][i];
                fail[chd[p][i]]=chd[fail[p]][i];
                word[chd[p][i]]|=word[fail[chd[p][i]]];
           }
           else
             chd[p][i]=chd[fail[p]][i];
    }
} 
void solve()
{
    memset(dp1,0,sizeof(dp1));  
    memset(dp2,0,sizeof(dp2));  
    dp1[0][0]=1;
    int Max=(1<<n);
    for(int k=0;k<len;k++)
    {
         for(int i=0;i<sz;i++)        
         for(int j=0;j<Max;j++)
          if(dp1[i][j])
          {
               for(int r=0;r<4;r++)             
                dp2[chd[i][r]][j|word[chd[i][r]]]=1;
          }
        memcpy(dp1,dp2,sizeof(dp2));  
        memset(dp2,0,sizeof(dp2));  
    }
    long long ans=-1;
    for(int i=0;i<sz;i++)        
    for(int j=0;j<Max;j++)
      if(dp1[i][j]) 
      {
           long long tmp=0;         
           for(int r=0;r<n;r++)              
            if(j&(1<<r)) tmp+=(long long)val[r];
           if(ans<tmp) ans=tmp; 
      }
     if(ans>=0) cout<<ans<<endl; 
     else cout<<"No Rabbit after 2012!"<<endl;
}

int main(int argc, char *argv[])
{
    sw['A']=0;
    sw['T']=1;
    sw['C']=2;
    sw['G']=3;
    while(cin>>n>>len)
    {
          sz=1;
          memset(chd[0],0,sizeof(chd[0]));
          for(int i=0;i<n;i++)  
          {
             cin>>s>>val[i];
             Ins(s,i);
          }
         ac();
         solve();  
    }
   // system("PAUSE");
    return EXIT_SUCCESS;
}