题意：容易理解...
分析:题目中给的模式串的个数最多为10个，于是想到用状态压缩dp来做，它的状态范围为1-2^9，所以最大为2^10-1，那我们可以用:dp[i][j][k]表示长度为i，在trie树上的状态为j，压缩后的状态为k时的情况，知道怎么压缩之后这道题就是一道简单的ac自动机+压缩dp题了。
代码实现：
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<queue> #include<cmath> using namespace std; struct node{ int next[4]; int fail; int flag; void init() { memset(next,0,sizeof(next)); fail=0; flag=0; } }a[1005]; int n,len,tot; int weight[15]; char keyword[105]; int dp[2][1005][1<<10]; void chushihua() { tot=0; a[0].init(); memset(dp,0,sizeof(dp)); } int hash(char x) { if(x=='A') return 0; else if(x=='C') return 1; else if(x=='G') return 2; else return 3; } void insert(char *str,int biaohao) { int p=0,index; for(;*str!=' ';str++) { index=hash(*str); if(a[p].next[index]==0) { a[++tot].init(); a[p].next[index]=tot; } p=a[p].next[index]; } a[p].flag=a[p].flag|(1<<biaohao);//状态标记 } void build_fail()//建立trie图 { queue<int>Q; int p,son,cur,i; Q.push(0); while(!Q.empty()) { p=Q.front(); Q.pop(); for(i=0;i<4;i++) { if(a[p].next[i]!=0) { son=a[p].next[i]; cur=a[p].fail; if(p==0) a[son].fail=0; else { while(cur&&a[cur].next[i]==0) cur=a[cur].fail; a[son].fail=a[cur].next[i]; } a[son].flag=a[son].flag|a[a[son].fail].flag; Q.push(son); } else a[p].next[i]=a[a[p].fail].next[i]; } } } int get_weight(int x) { int i,sum=0; for(i=0;i<n;i++) if(x&(1<<i)) sum+=weight[i]; return sum; } void solve() { int i,j,k,l,son,res,temp; dp[0][0][0]=1; for(i=1;i<=len;i++) { memset(dp[i&1],0,sizeof(dp[i&1])); for(j=0;j<=tot;j++) { for(l=0;l<(1<<n);l++) { if(dp[(i+1)&1][j][l]!=1) continue; for(k=0;k<4;k++) { son=a[j].next[k]; dp[i&1][son][l|a[son].flag]=1; } } } } res=-100000000; for(j=0;j<(1<<10);j++) for(i=0;i<=tot;i++) if(dp[len&1][i][j]==1) { temp=get_weight(j); if(res<temp) res=temp; } if(res<0) printf("No Rabbit after 2012! "); else printf("%d ",res); } int main() { int i; while(scanf("%d%d",&n,&len)!=EOF) { chushihua(); getchar(); for(i=0;i<n;i++) { scanf("%s%d",keyword,&weight[i]); insert(keyword,i); getchar(); } build_fail(); solve(); } return 0; }