【题意】：给出n(n<11)个基因串，每个基因串有对应的权值，构造一个长度为l的基因，问最大的权值为多少？重复的基因只能算一次。
【题解】：考虑到最多只有10个基因串，我们可以使用状态压缩。对于串之间的关系，我们可以建立对应的ac自动机，然后在ac自动机上进行状态压缩dp即可。
dp[i][j][k] i表示长度，j表示基因结尾状态，k表示所含基因的状态
转移方程，设son为j的孩子节点:
if(dp[i][j][k]) dp[i+1][son][k|T[son].id] = true;
实现的时候我用了滚动数组压缩空间，具体操作请看代码。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 const int kind = 4;
6 const int maxn = 250;
7 int score[15];
8 int root, tot;
9 char ch[25];
10 int n, m, l;
11 int que[maxn], head, tail;
12
13 struct Node {
14 int child[kind];
15 int fail;
16 int id;
17 void init() {
18 memset(child, 0, sizeof (child));
19 fail = -1, id = 0;
20 }
21 } T[maxn];
22
23 void init() {
24 root = tot = 0;
25 T[root].init();
26 }
27
28 int hash(char ch) {
29 if(ch == 'A') return 0;
30 else if(ch == 'C') return 1;
31 else if(ch == 'G') return 2;
32 else return 3;
33 }
34
35 void insert(char *s, int id) {//插入单词
36 int p = root, index;
37 while (*s) {
38 index = hash(*s);
39 if (!T[p].child[index]) {
40 T[++tot].init();
41 T[p].child[index] = tot;
42 }
43 p = T[p].child[index];
44 s++;
45 }
46 T[p].id |= 1 << id;
47 }
48
49 void build_ac_auto() {
50 head = tail = 0;
51 que[tail++] = root;
52 while (head < tail) {
53 int u = que[head++];
54 for (int i = 0; i < kind; i++) {
55 if (T[u].child[i]) {
56 int son = T[u].child[i];
57 int p = T[u].fail;
58 if (u == root) T[son].fail = root;
59 else {
60 T[son].fail = T[p].child[i];
61 T[son].id |= T[T[son].fail].id;
62 }
63 que[tail++] = son;
64 } else {//trie图，设定虚拟节点
65 int p = T[u].fail;
66 if (u == root) T[u].child[i] = root;
67 else T[u].child[i] = T[p].child[i];
68 }
69 }
70 }
71 }
72 bool dp[2][205][1<<10];//滚动数组,不用滚动也可以
73 void solve() {
74 int mask = 1 << n, now, next;
75 memset(dp, false, sizeof(dp));
76 dp[0][0][0] = true;
77 for(int i = 0; i < l; i++) {
78 now = i % 2;
79 next = (i + 1) % 2;
80 memset(dp[next], false, sizeof(dp[next]));
81 for(int j = 0; j <= tot; j++) {
82 for(int k = 0; k < mask; k++) {
83 if(dp[now][j][k]) {
84 for(int p = 0; p < kind; p++) {
85 int son = T[j].child[p];
86 dp[next][son][k|T[son].id] = true;
87 }
88 }
89 }
90 }
91 }
92 int ans = -(1 << 30);
93 now = l % 2;
94 for(int i = 0; i <= tot; i++) {
95 for(int j = 0; j < mask; j++) {
96 if(dp[now][i][j]) {
97 int t = 0;
98 for(int k = 0; k < n; k++) {
99 if(j & (1<< k)) t += score[k];
100 }
101 ans = max(ans, t);
102 }
103 }
104 }
105 if(ans < 0) printf("No Rabbit after 2012!\n");
106 else printf("%d\n", ans);
107 }
108
109 int main() {
110 while(~scanf("%d%d", &n, &l)) {
111 init();
112 for(int i = 0; i < n; i++) {
113 scanf("%s%d", ch, &score[i]);
114 insert(ch, i);
115 }
116 build_ac_auto();
117 solve();
118 }
119 return 0;
120 }