hdu2296Ring（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 1105
 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 = 26;
 19 char vir[110][15];
 20 string o[55][N];
 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[55][N];
 31     char s[N];
 32     public:
 33     void init()
 34     {
 35         fail[0] = 0;
 36         for(int i = 0 ; i < child_num ;i++)
 37         id[i+‘a‘] = i;
 38     }
 39     void reset()
 40     {
 41         memset(ch[0],0,sizeof(ch[0]));
 42         memset(val,0,sizeof(val));
 43         sz = 1;
 44     }
 45     void insert(char *a,int key)
 46     {
 47         int p = 0;
 48         for(; *a ; a++)
 49         {
 50             int d= id[*a];
 51             if(ch[p][d]==0)
 52             {
 53                 memset(ch[sz],0,sizeof(ch[sz]));
 54                 s[sz] = *a;
 55                 ch[p][d] = sz++;
 56             }
 57             p = ch[p][d];
 58         }
 59         val[p] = key;
 60     }
 61     void construct()
 62     {
 63         int i,head=0,tail = 0;
 64         for(i = 0; i  < child_num ;i++)
 65         {
 66             if(ch[0][i])
 67             {
 68                 fail[ch[0][i]] = 0;
 69                 Q[tail++] = ch[0][i];
 70             }
 71         }
 72         while(head!=tail)
 73         {
 74             int u = Q[head++];
 75             val[u]+=val[fail[u]];
 76             for(i = 0; i < child_num ; i++)
 77             {
 78                 if(ch[u][i])
 79                 {
 80                     fail[ch[u][i]] = ch[fail[u]][i];
 81                     Q[tail++] = ch[u][i];
 82                 }
 83                 else ch[u][i] = ch[fail[u]][i];
 84             }
 85         }
 86     }
 87     void work(int n)
 88     {
 89         int i,j,g;
 90         for(i = 0 ; i <= n ;i++)
 91             for(j = 0 ;j < sz ; j++)
 92             {
 93                 dp[i][j] = -INF;
 94                 o[i][j].clear();
 95             }
 96         dp[0][0] = 0;
 97         for(i = 0; i < n ;i++)
 98         {
 99             for(j = 0 ; j < sz ; j++)
100             for(g = 0 ; g < child_num ; g++)
101             {
102                 int tv = dp[i][j]+val[ch[j][g]];
103                 if(dp[i+1][ch[j][g]] <= tv)
104                 {
105                     if(dp[i+1][ch[j][g]]<tv||o[i+1][ch[j][g]]>o[i][j]+char(g+‘a‘))
106                     o[i+1][ch[j][g]] = o[i][j]+char(g+‘a‘);
107                     dp[i+1][ch[j][g]] = dp[i][j]+val[ch[j][g]];
108                 }
109             }
110         }
111         int ans = 0,y=0,x=0;
112         for(i = 0 ; i <=n ;i++)
113             for(j =0 ;j < sz ; j++)
114             {
115                 if(ans<=dp[i][j])
116                 {
117                     if(ans<dp[i][j]||(y==i&&o[i][j]<o[i][x]))
118                     {
119                         ans = dp[i][j];
120                         y = i;
121                         x = j;
122                     }
123                 }
124             }
125         g = 0;
126         if(ans==0) puts("");
127         else
128         cout<<o[y][x]<<endl;
129     }
130 }ac;
131 int main()
132 {
133     int n,i,m,t;
134     ac.init();
135     cin>>t;
136     while(t--)
137     {
138         scanf("%d%d",&n,&m);
139         ac.reset();
140         for(i = 1;i <= m ;i++)
141         scanf("%s",vir[i]);
142         for(i = 1; i <= m ;i++)
143         {
144             int v;
145             scanf("%d",&v);
146             ac.insert(vir[i],v);
147         }
148         ac.construct();
149         ac.work(n);
150     }
151     return 0;
152 }