Rescue the Rabbit
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2273 Accepted Submission(s): 667
Problem Description
Dr. X is a biologist, who likes rabbits very much and can do everything for them. 2012 is coming, and Dr. X wants to take some rabbits to Noah’s Ark, or there are no rabbits any more.
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.
Input
There are multiple test cases. For each case the first line is two integers n (1 ≤ n ≤ 10)，l (1 ≤ l ≤ 100), indicating the number of the particular gene segment and the length of rabbits’ genes.
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.
Output
For each test case, output an integer indicating the W value of the best rabbit. If we found this value is negative, you should output “No Rabbit after 2012!”.
Sample Input
2 4
ATG 4
TGC -3
1 6
TGC 4
4 1
A -1
T -2
G -3
C -4
Sample Output
4
4
No Rabbit after 2012!
Hint
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.
题目链接：HDU 4057
题意就是构造长度为$l$的字符串，如果包含给定的基因片段$str_i$，那么字符串的权值要加上$w_i$，而且一个基因片段最多只能算一次，求能构造出的最大权值。
考虑AC自动机上的DP，可以用$dp[i][j][s]$表示当前构造的字符串长度为$i$，走到AC自动机上第$j$个节点，包含的字符串二进制状态为$s$，设$j$可以走一步到下一个节点$v$，那么显然有：
由于是一个基因片段只能算一次，因此可以用前后变化值来求真正新增的权值，另外这题从转移方程来看显然是可以优化一下空间复杂度，用滚动数组即可（滚动之前一定要记得把下一个状态数组初始化，否则会出问题），否则内存占用巨大，当然还有速度比我这种做法快的即去更新可达状态，最后从可达状态中选出最优解
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1010;
struct Trie
{
int nxt[4];
int fail, cnt;
void init()
{
for (int i = 0; i < 4; ++i)
nxt[i] = -1;
fail = cnt = 0;
}
} L[N];
char s[N];
int id[90], w[10], dp[2][N][1 << 10], sz, val[1 << 10];
int n, l;
namespace AC
{
void init()
{
sz = 0;
L[sz++].init();
}
void ins(char s[], int len, int x)
{
int u = 0;
for (int i = 0; i < len; ++i)
{
int v = id[s[i]];
if (L[u].nxt[v] == -1)
{
L[sz].init();
L[u].nxt[v] = sz++;
}
u = L[u].nxt[v];
}
L[u].cnt |= (1 << x);
}
void build()
{
queue<int>Q;
L[0].fail = 0;
for (int i = 0; i < 4; ++i)
{
if (L[0].nxt[i] == -1)
L[0].nxt[i] = 0;
else
{
L[L[0].nxt[i]].fail = 0;
Q.push(L[0].nxt[i]);
}
}
while (!Q.empty())
{
int u = Q.front();
Q.pop();
int uf = L[u].fail;
if (L[uf].cnt)
L[u].cnt |= L[uf].cnt;
for (int i = 0; i < 4; ++i)
{
if (L[u].nxt[i] == -1)
L[u].nxt[i] = L[uf].nxt[i];
else
{
L[L[u].nxt[i]].fail = L[uf].nxt[i];
Q.push(L[u].nxt[i]);
}
}
}
}
}
inline int getval(int st)
{
int ret = 0;
for (int i = 0; i < n; ++i)
{
if (st & (1 << i))
ret += w[i];
}
return ret;
}
int main(void)
{
id['A'] = 0;
id['T'] = 1;
id['G'] = 2;
id['C'] = 3;
int i, j, k;
while (~scanf("%d%d", &n, &l))
{
AC::init();
for (i = 0; i < n; ++i)
{
scanf("%s %d", s, &w[i]);
AC::ins(s, strlen(s), i);
}
AC::build();
CLR(dp, -INF);
dp[0][0][0] = 0;
int R = (1 << n);
for (i = 0; i < R; ++i)
val[i] = getval(i);
int now = 0, nxt = 1;
for (i = 0; i < l; ++i) //100
{
CLR(dp[nxt], -INF);
for (j = 0; j < sz; ++j) //1000
{
for (int s = 0; s < R; ++s)
{
if (dp[now][j][s] == -INF)
continue;
for (k = 0; k < 4; ++k)
{
int v = L[j].nxt[k];
int news = (s | L[v].cnt);
dp[nxt][v][news] = max(dp[nxt][v][news], dp[now][j][s] + val[news] - val[s]);
}
}
}
swap(now, nxt);
}
int ans = -INF;
for (i = 0; i < sz; ++i)
for (j = 0; j < R; ++j)
if (dp[now][i][j] > ans)
ans = dp[now][i][j];
ans < 0 ? puts("No Rabbit after 2012!") : printf("%d\n", ans);
}
return 0;
}