首页 > 代码库 > hdu4057Rescue the Rabbit(ac自动机+dp)
hdu4057Rescue the Rabbit(ac自动机+dp)
链接
当时是因为没有做出来这道题才开了自动机的专题,现在看看还是比较简单的。
因为每个病毒串只算一次,只有10个病毒串,可以状压一下哪些状态是可以达到的,最后取一个最大值。
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。