【題意】：給出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 }