地址：http://acm.hdu.edu.cn/showproblem.php?pid=4057
题目：
Rescue the Rabbit
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2233 Accepted Submission(s): 653
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.
ATG 4
TGC -3
1 6
TGC 4
4 1
A -1
T -2
G -3
C -4
4
No Rabbit after 2012!
case 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.
思路：
dp[i][j][s]表示长度为i的串走到第j个节点时状态为s时是否可行。
如果用dp[i][j][s] 表示长度为i的串走到第j个节点时状态为s时的最小花费会Tle，因为常数会大十倍
而且需要状压，不然mle。
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std; const int INF=0x3f3f3f3f;
struct AC_auto
{
const static int LetterSize = ;
const static int TrieSize = LetterSize * ( 1e3 + ); int tot,root,fail[TrieSize],end[TrieSize],next[TrieSize][LetterSize];
bool dp[][TrieSize][<<];
int newnode(void)
{
memset(next[tot],-,sizeof(next[tot]));
end[tot] = ;
return tot++;
} void init(void)
{
tot = ;
root = newnode();
} int getidx(char x)
{
if(x=='A') return ;
else if(x=='C') return ;
else if(x=='G') return ;
return ;
} void insert(char *ss,int x)
{
int len = strlen(ss);
int now = root;
for(int i = ; i < len; i++)
{
int idx = getidx(ss[i]);
if(next[now][idx] == -)
next[now][idx] = newnode();
now = next[now][idx];
}
end[now]|=x;
} void build(void)
{
queue<int>Q;
fail[root] = root;
for(int i = ; i < LetterSize; i++)
if(next[root][i] == -)
next[root][i] = root;
else
fail[next[root][i]] = root,Q.push(next[root][i]);
while(Q.size())
{
int now = Q.front();Q.pop();
for(int i = ; i < LetterSize; i++)
if(next[now][i] == -) next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
end[next[now][i]]|=end[fail[next[now][i]]];
Q.push(next[now][i]);
}
}
} int match(char *ss)
{
int len,now,res;
len = strlen(ss),now = root,res = ;
for(int i = ; i < len; i++)
{
int idx = getidx(ss[i]);
int tmp = now = next[now][idx];
while(tmp)
{
res += end[tmp];
end[tmp] = ;//°´ÌâÄ¿ÐÞ¸Ä
tmp = fail[tmp];
}
}
return res;
} int go(int n,int m,int *v)
{
int ans=-0x3f3f3f3f,now=,pre=;
memset(dp[pre],,sizeof dp[pre]);
dp[][][]=;
for(int i=,mx=<<m;i<n;i++)
{
memset(dp[now],,sizeof dp[now]);
for(int j=;j<tot;j++)
for(int s=;s<mx;s++)
for(int k=;dp[pre][j][s]&&k<LetterSize;k++)
dp[now][next[j][k]][s|end[next[j][k]]]=;
swap(now,pre);
}
for(int i=,mx=<<m;i<tot;i++)
for(int j=;j<mx;j++)
if(dp[pre][i][j])
{
int tmp=;
for(int k=;k<m;k++)
if(j&(<<k))
tmp+=v[k];
ans=max(ans,tmp);
}
return ans;
}
void debug()
{
for(int i = ;i < tot;i++)
{
printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
for(int j = ;j < LetterSize;j++)
printf("%3d",next[i][j]);
printf("]\n");
}
}
};
AC_auto ac;
char ss[];
int v[];
int main(void)
{
//freopen("in.acm","r",stdin);
int n,m;
while(~scanf("%d%d",&m,&n))
{
ac.init();
for(int i=;i<m;i++)
scanf("%s%d",ss,v+i),ac.insert(ss,<<i);
ac.build();
int ans=ac.go(n,m,v);
if(ans<) printf("No Rabbit after 2012!\n");
else printf("%d\n",ans);
}
return ;
}