Rescue the Rabbit
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2036 Accepted Submission(s): 591
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.
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.
# include<iostream>
# include<cstdio>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std; const short N=1005;
const short INF=0x7fff; short ch[N][4];
short sz;
short val[N]; void init()
{
sz=0;
memset(ch,-1,sizeof(ch));
memset(val,0,sizeof(val));
} short idx(char c)
{
if(c=='A') return 0;
else if(c=='T') return 1;
else if(c=='C') return 2;
else if(c=='G') return 3;
} void insert(char *s,short x)
{
short r=0;
short n=strlen(s);
for(short i=0;i<n;++i){
short c=idx(s[i]);
if(ch[r][c]==-1) ch[r][c]=++sz;
r=ch[r][c];
}
val[r]=x;
} void getFail()
{
short *fail=new short[sz+1];
queue<short>q;
fail[0]=0;
for(short i=0;i<4;++i){
if(ch[0][i]==-1)
ch[0][i]=0;
else{
fail[ch[0][i]]=0;
q.push(ch[0][i]);
}
}
while(!q.empty())
{
short u=q.front();
q.pop();
val[u]|=val[fail[u]];
for(short i=0;i<4;++i){
if(ch[u][i]==-1)
ch[u][i]=ch[fail[u]][i];
else{
fail[ch[u][i]]=ch[fail[u]][i];
q.push(ch[u][i]);
}
}
}
delete []fail;
} char s[6]; void solve(short n,short m,short *w)
{
short*** dp=new short**[2];
for(short i=0;i<2;++i){
dp[i]=new short*[sz+1];
for(short j=0;j<=sz;++j){
dp[i][j]=new short[1<<n];
}
} for(short i=0;i<=sz;++i) for(short j=0;j<(1<<n);++j)
dp[0][i][j]=-INF;
dp[0][0][0]=0;
short flag=1;
for(short i=0;i<m;++i,flag^=1){
for(short j=0;j<=sz;++j)
for(short k=0;k<(1<<n);++k)
dp[flag][j][k]=-INF;
for(short j=0;j<=sz;++j){
for(short k=0;k<(1<<n);++k){
if(dp[flag^1][j][k]==-INF)
continue;
for(short c=0;c<4;++c){
short v=ch[j][c];
short tempw=0;
for(short l=0;l<n;++l){
if(!(k&(1<<l))&&(val[v]&(1<<l)))
tempw+=w[l];
}
short &nxt=dp[flag][v][k|val[v]];
if(nxt<dp[flag^1][j][k]+tempw)
nxt=dp[flag^1][j][k]+tempw;
}
}
}
}
short ans=-INF;
for(short i=0;i<=sz;++i)
for(short j=0;j<(1<<n);++j)
ans=max(ans,dp[flag^1][i][j]);
if(ans>=0)
cout<<ans<<endl;
else
printf("No Rabbit after 2012!\n"); for(short i=0;i<2;++i){
for(short j=0;j<=sz;++j){
delete []dp[i][j];
}
delete []dp[i];
}
delete dp;
} int main()
{
short n,m;
while(cin>>n>>m)
{
init();
short *w=new short[n];
for(short i=0;i<n;++i){
scanf("%s%d",s,w+i);
insert(s,1<<i);
}
getFail();
solve(n,m,w);
delete []w;
}
return 0;
}
代码二：
# include<iostream>
# include<cstdio>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std; const int N=1005;
const int INF=0x7fff; int ch[N][4];
int sz;
int val[N]; void init()
{
sz=0;
memset(ch,-1,sizeof(ch));
memset(val,0,sizeof(val));
} int idx(char c)
{
if(c=='A') return 0;
else if(c=='T') return 1;
else if(c=='C') return 2;
else if(c=='G') return 3;
} void insert(char *s,int x)
{
int r=0;
int n=strlen(s);
for(int i=0;i<n;++i){
int c=idx(s[i]);
if(ch[r][c]==-1) ch[r][c]=++sz;
r=ch[r][c];
}
val[r]=x;
} void getFail()
{
int *fail=new int[sz+1];
queue<int>q;
fail[0]=0;
for(int i=0;i<4;++i){
if(ch[0][i]==-1)
ch[0][i]=0;
else{
fail[ch[0][i]]=0;
q.push(ch[0][i]);
}
}
while(!q.empty())
{
int u=q.front();
q.pop();
val[u]|=val[fail[u]];
for(int i=0;i<4;++i){
if(ch[u][i]==-1)
ch[u][i]=ch[fail[u]][i];
else{
fail[ch[u][i]]=ch[fail[u]][i];
q.push(ch[u][i]);
}
}
}
delete []fail;
} char s[6];
int w[10];
int dp[2][N+1][1<<10]; int get(int s,int n)
{
int res=0;
for(int i=0;i<n;++i)
if(s&(1<<i)) res+=w[i];
return res;
} void solve(int n,int m)
{
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
int flag=1;
for(int i=0;i<m;++i,flag^=1){
memset(dp[flag],0,sizeof(dp[flag]));
for(int j=0;j<=sz;++j){
for(int k=0;k<(1<<n);++k) if(dp[flag^1][j][k]){
for(int c=0;c<4;++c)
dp[flag][ch[j][c]][k|val[ch[j][c]]]=1;
}
}
}
int ans=-INF;
for(int s=0;s<(1<<n);++s){
int temp=get(s,n);
for(int i=0;i<=sz;++i){
if(dp[flag^1][i][s]&&temp>ans){
ans=temp;
break;
}
}
}
if(ans>=0)
cout<<ans<<endl;
else
printf("No Rabbit after 2012!\n");
} int main()
{
int n,m;
while(cin>>n>>m)
{
init();
for(int i=0;i<n;++i){
scanf("%s%d",s,w+i);
insert(s,1<<i);
}
getFail();
solve(n,m);
}
return 0;
}