首页 > 代码库 > HDU 4057 Rescue the Rabbit (AC自动机+DP)
HDU 4057 Rescue the Rabbit (AC自动机+DP)
http://acm.hdu.edu.cn/showproblem.php?pid=4057
Rescue the RabbitTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1482 Accepted Submission(s): 430
Problem Description
Dr. X is a biologist, who likes rabbits very much and can do everything for them. 2012 is coming, and Dr. X wants to take some rabbits to Noah‘s Ark, or there are no rabbits any more.
A rabbit‘s genes can be expressed as a string whose length is l (1 ≤ l ≤ 100) containing only ‘A‘, ‘G‘, ‘T‘, ‘C‘. There is no doubt that Dr. X had a in-depth research on the rabbits‘ genes. He found that if a rabbit gene contained a particular gene segment, we could consider it as a good rabbit, or sometimes a bad rabbit. And we use a value W to measure this index.
We can make a example, if a rabbit has gene segment "ATG", its W would plus 4; and if has gene segment "TGC", its W plus -3. So if a rabbit‘s gene string is "ATGC", its W is 1 due to ATGC contains both "ATG"(+4) and "TGC"(-3). And if another rabbit‘s gene string is "ATGATG", its W is 4 due to one gene segment can be calculate only once.
Because there are enough rabbits on Earth before 2012, so we can assume we can get any genes with different structure. Now Dr. X want to find a rabbit whose gene has highest W value. There are so many different genes with length l, and Dr. X is not good at programming, can you help him to figure out the W value of the best rabbit.
A rabbit‘s genes can be expressed as a string whose length is l (1 ≤ l ≤ 100) containing only ‘A‘, ‘G‘, ‘T‘, ‘C‘. There is no doubt that Dr. X had a in-depth research on the rabbits‘ genes. He found that if a rabbit gene contained a particular gene segment, we could consider it as a good rabbit, or sometimes a bad rabbit. And we use a value W to measure this index.
We can make a example, if a rabbit has gene segment "ATG", its W would plus 4; and if has gene segment "TGC", its W plus -3. So if a rabbit‘s gene string is "ATGC", its W is 1 due to ATGC contains both "ATG"(+4) and "TGC"(-3). And if another rabbit‘s gene string is "ATGATG", its W is 4 due to one gene segment can be calculate only once.
Because there are enough rabbits on Earth before 2012, so we can assume we can get any genes with different structure. Now Dr. X want to find a rabbit whose gene has highest W value. There are so many different genes with length l, and Dr. X is not good at programming, can you help him to figure out the W value of the best rabbit.
Input
There are multiple test cases. For each case the first line is two integers n (1 ≤ n ≤ 10),l (1 ≤ l ≤ 100), indicating the number of the particular gene segment and the length of rabbits‘ genes.
The next n lines each line contains a string DNAi and an integer wi (|wi| ≤ 100), indicating this gene segment and the value it can contribute to a rabbit‘s W.
The next n lines each line contains a string DNAi and an integer wi (|wi| ≤ 100), indicating this gene segment and the value it can contribute to a rabbit‘s W.
Output
For each test case, output an integer indicating the W value of the best rabbit. If we found this value is negative, you should output "No Rabbit after 2012!".
Sample Input
2 4 ATG 4 TGC -3 1 6 TGC 4 4 1 A -1 T -2 G -3 C -4
Sample Output
4 4 No Rabbit after 2012!Hintcase 1:we can find a rabbit whose gene string is ATGG(4), or ATGA(4) etc. case 2:we can find a rabbit whose gene string is TGCTGC(4), or TGCCCC(4) etc. case 3:any gene string whose length is 1 has a negative W.
Author
HONG, Qize
Source
2011 Asia Dalian Regional Contest
题意:
有ATCG4个字母,要求构成一个长度为l的字符串,给出n个模式串及其权值,问能构成的字符串中最大的权值和是多少,每个模式串只计算一次。
分析:
很容易想到是AC自动机。我们在AC自动机上找到长度为l的可行方案,并求出最大值即可。用dp[i][j][k]表示字符串长度为i时,AC自动机上第j个结点是否可达状态k。因为模式串只有10种,所以最多有2^10个状态,状压一下就行了,然后就是长度为i的字符串只由第i-1个变过来,所以可以用滚动数组。
/* * * Author : fcbruce <fcbruce8964@gmail.com> * * Time : Thu 13 Nov 2014 08:23:41 PM CST * */ #include <cstdio> #include <iostream> #include <sstream> #include <cstdlib> #include <algorithm> #include <ctime> #include <cctype> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #ifdef _WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define maxm #define maxn 1007 using namespace std; char gene[17][233]; int w[17]; int dp[2][maxn][2333]; int q[maxn<<1]; const int maxsize = 4; struct ACauto { int ch[maxn][maxsize]; int val[maxn],last[maxn],nex[maxn]; int sz; ACauto() { sz=1; val[0]=0; memset(ch[0],0,sizeof ch[0]); } void clear() { sz=1; val[0]=0; memset(ch[0],0,sizeof ch[0]); } int idx(char c) { switch (c) { case 'A': return 0; case 'T': return 1; case 'C': return 2; case 'G': return 3; } } void insert(const char *s,int v) { int u=0; for (int i=0;s[i]!='\0';i++) { int c=idx(s[i]); if (ch[u][c]==0) { memset(ch[sz],0,sizeof ch[sz]); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=v; } void get_fail() { int f=0,r=-1; nex[0]=0; for (itn c=0;c<maxsize;c++) { int u=ch[0][c]; if (u!=0) { nex[u]=0; q[++r]=u; } } while (f<=r) { int x=q[f++]; for (int c=0;c<maxsize;c++) { int u=ch[x][c]; if (u==0) { ch[x][c]=ch[nex[x]][c]; continue; } q[++r]=u; int v=nex[x]; nex[u]=ch[v][c]; val[u]|=val[nex[u]]; } } } int calc(int x,int n) { int score=0; for (int i=0;i<n;i++) if (x&(1<<i)) score+=w[i]; return score; } int go(int l,int n) { memset(dp,0,sizeof dp); dp[0][0][0]=true; int x=1; for (int i=1;i<=l;i++,x^=1) { memset(dp[x],0,sizeof dp[x]); for (int j=0;j<sz;j++) for (int k=0;k<4;k++) for (int l=0;l<(1<<n);l++) if (dp[x^1][j][l]) dp[x][ch[j][k]][l|val[ch[j][k]]]=true; } int MAX=-1; for (int i=0;i<(1<<n);i++) { int cur=calc(i,n); if (cur<=MAX) continue; for (int j=0;j<=sz;j++) if (dp[x^1][j][i]) { MAX=cur; break; } } return MAX; } }acauto; int main() { #ifdef FCBRUCE freopen("/home/fcbruce/code/t","r",stdin); #endif // FCBRUCE int n,l; while (scanf("%d%d",&n,&l)==2) { acauto.clear(); for (int i=0;i<n;i++) { scanf("%s %d",gene[i],w+i); acauto.insert(gene[i],1<<i); } acauto.get_fail(); int MAX=acauto.go(l,n); if (MAX>=0) printf("%d\n",MAX); else puts("No Rabbit after 2012!"); } return 0; }
HDU 4057 Rescue the Rabbit (AC自动机+DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。