HDU 4057 Rescue the Rabbit(AC自动机+DP)

一个数组开小了一点点，一直提示wa，郁闷，这题比上个题简单一点。
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <queue>
  5 #include <algorithm>
  6 #include <cstdlib>
  7 using namespace std;
  8 #define N 1001
  9 #define INF 1000000
 10 int trie[N][5];
 11 int que[N];
 12 int o[1<<10];
 13 int flag[N];
 14 int fail[N];
 15 int dp1[N][1<<10];
 16 int dp2[N][1<<10];
 17 int t,n;
 18 int lowbit(int t)
 19 {
 20     return t&(-t);
 21 }
 22 void CL()
 23 {
 24     t = 1;
 25     memset(trie,-1,sizeof(trie));
 26     memset(o,0,sizeof(o));
 27     memset(flag,0,sizeof(flag));
 28 }
 29 int judge(char s)
 30 {
 31     switch(s)
 32     {
 33     case'A':
 34         return 0;
 35     case'C':
 36         return 1;
 37     case'G':
 38         return 2;
 39     case'T':
 40         return 3;
 41     }
 42     return 0;
 43 }
 44 void insert(char *str,int x,int j)
 45 {
 46     int i,len,root;
 47     root = 0;
 48     len = strlen(str);
 49     for(i = 0; i < len; i ++)
 50     {
 51         if(trie[root][judge(str[i])] == -1)
 52             trie[root][judge(str[i])] = t ++;
 53         root = trie[root][judge(str[i])];
 54     }
 55     flag[root] = 1<<j;
 56 }
 57 void build_ac()
 58 {
 59     int head,tail,front,i;
 60     head = tail = 0;
 61     for(i = 0; i < 4; i ++)
 62     {
 63         if(trie[0][i] != -1)
 64         {
 65             fail[trie[0][i]] = 0;
 66             que[tail++] = trie[0][i];
 67         }
 68         else
 69         {
 70             trie[0][i] = 0;
 71         }
 72     }
 73     while(head != tail)
 74     {
 75         front = que[head++];
 76         flag[front] |= flag[fail[front]];
 77         for(i = 0; i < 4; i ++)
 78         {
 79             if(trie[front][i] != -1)
 80             {
 81                 que[tail++] = trie[front][i];
 82                 fail[trie[front][i]] = trie[fail[front]][i];
 83             }
 84             else
 85             {
 86                 trie[front][i] = trie[fail[front]][i];
 87             }
 88         }
 89     }
 90 }
 91 int main()
 92 {
 93     int m,i,j,u,x,len,k;
 94     int sc[101];
 95     char str[1001];
 96     while(scanf("%d%d",&n,&m)!=EOF)
 97     {
 98         CL();
 99         for(i = 0; i < n; i ++)
100         {
101             scanf("%s%d",str,&x);
102             len = strlen(str);
103             if(len > m)
104             {
105                 i --;
106                 n -- ;
107                 continue;
108             }
109             sc[i] = x;
110             insert(str,x,i);
111         }
112         for(i = 0;i < n;i ++)
113         o[1<<i] = sc[i];
114         for(i = 1; i < 1<<n;i ++)
115         {
116             o[i] = o[i-lowbit(i)] + o[lowbit(i)];
117         }
118         build_ac();
119         for(j = 0; j < t; j ++)
120         {
121             for(k = 0; k < (1<<n); k ++)
122             {
123                 dp1[j][k] = 0;
124                 dp2[j][k] = 0;
125             }
126         }
127         dp1[0][0] = 1;
128         for(i = 0; i < m; i ++)
129         {
130             for(j = 0; j < t; j ++)
131             {
132                 for(k = 0;k < (1<<n);k ++)
133                 {
134                     if(dp1[j][k] == 0) continue;
135                     int temp;
136                     for(u = 0;u < 4;u ++)
137                     {
138                         temp = k|flag[trie[j][u]];
139                         dp2[trie[j][u]][temp] += dp1[j][k];
140                     }
141                 }
142             }
143             for(j = 0; j < t; j ++)
144             {
145                 for(k = 0; k < (1<<n); k ++)
146                 {
147                     dp1[j][k] = dp2[j][k];
148                     dp2[j][k] = 0;
149                 }
150             }
151         }
152         int ans = -INF;
153         for(j = 0;j < t;j ++)
154         {
155             for(k = 0;k <(1<<n);k ++)
156             {
157                 if(dp1[j][k])
158                 ans = max(ans,o[k]);
159             }
160         }
161         if(ans >= 0)
162         printf("%d
",ans);
163         else
164         printf("No Rabbit after 2012!
");
165     }
166     return 0;
167 }