hdu4057Rescue the Rabbit(ac自动机+dp)

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 #include<string>
 11 using namespace std;
 12 #define N 1005
 13 #define LL long long
 14 #define INF 0xfffffff
 15 const double eps = 1e-8;
 16 const double pi = acos(-1.0);
 17 const double inf = ~0u>>2;
 18 const int child_num = 4;
 19 char vir[115];
 20 int v[12];
 21 class AC
 22 {
 23     private:
 24     int ch[N][child_num];
 25     int fail[N];
 26     int Q[N];
 27     int val[N];
 28     int sz;
 29     int id[128];
 30     int dp[2][N][1<<10];
 31     char s[N];
 32     public:
 33     void init()
 34     {
 35         fail[0] = 0;
 36         id[‘A‘] = 0,id[‘G‘] = 1,id[‘T‘] = 2,id[‘C‘] = 3;
 37     }
 38     void reset()
 39     {
 40         memset(ch[0],0,sizeof(ch[0]));
 41         memset(val,0,sizeof(val));
 42         sz = 1;
 43     }
 44     void insert(char *a,int key)
 45     {
 46         int p = 0;
 47         for(; *a ; a++)
 48         {
 49             int d= id[*a];
 50             if(ch[p][d]==0)
 51             {
 52                 memset(ch[sz],0,sizeof(ch[sz]));
 53                 s[sz] = *a;
 54                 ch[p][d] = sz++;
 55             }
 56             p = ch[p][d];
 57         }
 58         val[p] = (1<<key);
 59     }
 60     void construct()
 61     {
 62         int i,head=0,tail = 0;
 63         for(i = 0; i  < child_num ;i++)
 64         {
 65             if(ch[0][i])
 66             {
 67                 fail[ch[0][i]] = 0;
 68                 Q[tail++] = ch[0][i];
 69             }
 70         }
 71         while(head!=tail)
 72         {
 73             int u = Q[head++];
 74             val[u]|=val[fail[u]];
 75             for(i = 0; i < child_num ; i++)
 76             {
 77                 if(ch[u][i])
 78                 {
 79                     fail[ch[u][i]] = ch[fail[u]][i];
 80                     Q[tail++] = ch[u][i];
 81                 }
 82                 else ch[u][i] = ch[fail[u]][i];
 83             }
 84         }
 85     }
 86     void work(int n,int m)
 87     {
 88         int i,j,g;
 89         memset(dp,0,sizeof(dp));
 90         dp[0][0][0] = 1;
 91         for(i = 0 ;i < n ;i++)
 92         {
 93             memset(dp[(i+1)%2],0,sizeof(dp[(i+1)%2]));
 94             for(j = 0 ;j < sz ; j++)
 95             {
 96                 for(int e = 0 ; e < (1<<m) ; e++)
 97                 {
 98                     if(!dp[i%2][j][e]) continue;
 99                     for(g = 0 ; g < child_num ; g++)
100                     {
101                         int o = val[ch[j][g]];
102                         dp[(i+1)%2][ch[j][g]][e|o] = dp[i%2][j][e];
103                     }
104                 }
105             }
106         }
107         int cnt = -INF;
108         for(i = 0 ;i < sz ; i++)
109         {
110             for(j = 0 ;j < (1<<m) ; j++)
111             {
112                 int ans = 0;
113                 if(!dp[n%2][i][j]) continue;
114                 for(g = 0 ; g < m ;g++)
115                 {
116                     if(j&(1<<g))
117                     ans+=v[g];
118                 }
119                 cnt = max(ans,cnt);
120             }
121         }
122         if(cnt<0)
123         puts("No Rabbit after 2012!");
124         else
125         printf("%d\n",cnt);
126     }
127 }ac;
128 int main()
129 {
130     int n,i,m;
131     ac.init();
132     while(scanf("%d%d",&m,&n)!=EOF)
133     {
134         ac.reset();
135         for(i = 1;i <= m ;i++)
136         {
137             scanf("%s%d",vir,&v[i-1]);
138             ac.insert(vir,i-1);
139         }
140         ac.construct();
141         ac.work(n,m);
142     }
143     return 0;
144 }