Lost’s revenge
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 4543 Accepted Submission(s): 1271
Problem Description
Lost and AekdyCoin are friends. They always play “number game”(A boring game based on number theory) together. We all know that AekdyCoin is the man called “nuclear weapon of FZU,descendant of Jingrun”, because of his talent in the field of number theory. So Lost had never won the game. He was so ashamed and angry, but he didn’t know how to improve his level of number theory.
One noon, when Lost was lying on the bed, the Spring Brother poster on the wall(Lost is a believer of Spring Brother) said hello to him! Spring Brother said, “I’m Spring Brother, and I saw AekdyCoin shames you again and again. I can’t bear my believers were being bullied. Now, I give you a chance to rearrange your gene sequences to defeat AekdyCoin!”.
It’s soooo crazy and unbelievable to rearrange the gene sequences, but Lost has no choice. He knows some genes called “number theory gene” will affect one “level of number theory”. And two of the same kind of gene in different position in the gene sequences will affect two “level of number theory”, even though they overlap each other. There is nothing but revenge in his mind. So he needs you help to calculate the most “level of number theory” after rearrangement.
Input
There are less than 30 testcases.
For each testcase, first line is number of “number theory gene” N(1<=N<=50). N=0 denotes the end of the input file.
Next N lines means the “number theory gene”, and the length of every “number theory gene” is no more than 10.
The last line is Lost’s gene sequences, its length is also less or equal 40.
All genes and gene sequences are only contains capital letter ACGT.
Output
For each testcase, output the case number(start with 1) and the most “level of number theory” with format like the sample output.
Sample Input
3
AC
CG
GT
CGAT
1
AA
AAA
0
Sample Output
Case 1: 3
Case 2: 2
题目链接：HDU 3341
起初很容易想到用$dp[i][j][k][s][u]$表示当前构造的字符串有$i$个$\mathbf A$，$j$个$\mathbf C$，$k$个$\mathbf G$，$s$个$\mathbf T$，且当前字符串结尾在节点$u$上，由于存在合法性问题，一开始$dp$数组可以初始化成$-\infty$
转移方程就是
但是这样的空间复杂度是$40^4*500$数组开不下，但是题目里显然四种字符加起来也就$40$个，那么可以考虑把前四维压缩到一维，可以压掉大部分情况下用不到的空间。
如果知道地址偏移量这个概念，那么就可以知道高维数组都可以通过计算其偏移量压缩成一维数组，公式如下：
设四维数组$A[a][b][c][d]$，下标均从$0$开始，此时如果要求$A[i][j][x][y]$，那么在压缩之后$A[i][j][x][y] = A+i*(b*c*d)+j*(c*d)+x*d+y*1$
然后大概前四维压缩需要$10*11^3+10*11^2+10*11^1+10*11^0 = 14640$，算上后面记录节点的一维，五六百万的数组刚好可以用，最后过程中注意减少地址计算的次数，否则容易超时
代码：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
157
158
159
160
161
162
163
164
165
166
167
168
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 510;
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[42];
int cnt[4], id[90], sz;
int dp[14650][N];
namespace ac
{
void init()
{
sz = 0;
L[sz++].init();
}
void ins(char s[], int len)
{
int u = 0;
for (int i = 0; i < len; ++i)
{
int v = id[(int)s[i]];
if (L[u].nxt[v] == -1)
{
L[sz].init();
L[u].nxt[v] = sz++;
}
u = L[u].nxt[v];
}
++L[u].cnt;
}
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]);
}
}
}
}
}
int main(void)
{
int n, i, j, k;
int T = 0;
id['A'] = 0;
id['C'] = 1;
id['G'] = 2;
id['T'] = 3;
while (~scanf("%d", &n) && n)
{
ac::init();
for (int i = 0; i < n; ++i)
{
scanf("%s", s);
ac::ins(s, strlen(s));
}
ac::build();
scanf("%s", s);
int len = strlen(s);
for (i = 0; i < 4; ++i)
cnt[i] = 0;
for (i = 0; i < len; ++i)
++cnt[id[(int)s[i]]];
CLR(dp, -INF);
dp[0][0] = 0;
int Base[4] =
{
(cnt[1] + 1) * (cnt[2] + 1) * (cnt[3] + 1),
(cnt[2] + 1) * (cnt[3] + 1),
(cnt[3] + 1),
1
};
for (i = 0; i <= cnt[0]; ++i)
{
for (j = 0; j <= cnt[1]; ++j)
{
for (k = 0; k <= cnt[2]; ++k)
{
for (int s = 0; s <= cnt[3]; ++s)
{
for (int u = 0; u < sz; ++u)
{
int st = i * Base[0] + j * Base[1] + k * Base[2] + s * Base[3];
if (dp[st][u] < 0)
continue;
for (int l = 0; l < 4; ++l)
{
if (l == 0 && i >= cnt[0])
continue;
if (l == 1 && j >= cnt[1])
continue;
if (l == 2 && k >= cnt[2])
continue;
if (l == 3 && s >= cnt[3])
continue;
int v = L[u].nxt[l];
int &dp_nxt = dp[st + Base[l]][v];
dp_nxt = max(dp_nxt, dp[st][u] + L[v].cnt);
}
}
}
}
}
}
int ans = 0;
int F = cnt[0] * Base[0] + cnt[1] * Base[1] + cnt[2] * Base[2] + cnt[3] * Base[3];
for (i = 0; i < sz; ++i)
ans = max(ans, dp[F][i]);
printf("Case %d: %d\n", ++T, ans);
}
return 0;
}