hdu 4057
一样的思路，设$dp(i,j,S)$为考虑了$i$个字符，在自动机$j$点上，基因状态$S$时的最大权。
转移则$dp(i,v,S | zt(v)) = max(dp(i - 1, j, S) + \sum val_i \in zt(v))$
注意$\sum val_i \in zt(v))$，$S$如果相应位置有则不用累加
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 * 10 + 5;
const int fINF = -1000000000;
int n, L, sz = 100 * 10;
char s[105];
int f[MAXN], val[MAXN], ch[MAXN][10], zt[MAXN], dp[2][MAXN][(1 << 11) + 100];
int idx(char x) {
switch (x) {
case 'A' : return 0;
case 'G' : return 1;
case 'T' : return 2;
case 'C' : return 3;
}
return -1;
}
void insert(char *s, int ith) {
int now = 0, len = strlen(s);
for (int i = 0; i < len; i++) {
int c = idx(s[i]);
if (!ch[now][c]) ch[now][c] = ++sz;
now = ch[now][c];
if (i == len - 1) zt[now] |= (1 << (ith - 1));
}
}
void getFail() {
queue<int> q;
f[0] = 0;
for (int c = 0; c < 4; c++) {
int v = ch[0][c];
if (v) q.push(v), f[v] = 0;
}
while (!q.empty()) {
int u = q.front(); q.pop();
for (int c = 0; c < 4; c++) {
int v = ch[u][c];
if (!v) {ch[u][c] = ch[f[u]][c]; continue;}
q.push(v);
int j = f[u]; while (j && !ch[j][c]) j = f[j];
f[v] = ch[j][c];
zt[v] |= zt[ch[j][c]];
}
}
}
int calscore(int s, int zzt) {
int ret = 0, ws = -1, tmpS = s, tmpZ = zzt;
do {
ws++;
if (!(tmpS & 1) && (tmpZ & 1)) ret += val[ws + 1];
tmpS >>= 1, tmpZ >>= 1;
} while (tmpZ != 0);
return ret;
}
void cal() {
dp[0][0][0] = 0;
int x = 1;
for (int i = 1; i <= L; i++) {
for (int j = 0; j <= sz; j++)
for (int S = 0; S < (1 << 10); S++) dp[x][j][S] = fINF;
for (int j = 0; j <= sz; j++) {
for (int S = 0; S < (1 << 10); S++) {
if (dp[x ^ 1][j][S] == fINF) continue;
for (int c = 0; c < 4; c++) {
int v = ch[j][c];
dp[x][v][S | zt[v]] = max(dp[x][v][S | zt[v]], dp[x ^ 1][j][S] + calscore(S, zt[v]));
}
}
}
x ^= 1;
}
}
void clean() {
for (int i = 0; i <= sz; i++) {
for (int j = 0; j < 4; j++) ch[i][j] = 0;
for (int k = 0; k <= (1 << 10); k++) dp[0][i][k] = dp[1][i][k] = fINF;
f[i] = val[i] = zt[i] = 0;
}
sz = 0;
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
scanf("%s %d", s, &val[i]);
insert(s, i);
}
getFail(), cal();
int taki = fINF;
for (int j = 0; j <= sz; j++)
for (int k = 0; k < (1 << 10); k++) taki = max(taki, dp[L % 2][j][k]);
if (taki < 0) printf("No Rabbit after 2012!\n"); else printf("%d\n", taki);
}
int main() {
while (scanf("%d%d", &n, &L) == 2) solve();
return 0;
}
/*
4 3
A -1
G -4
T 8
C 10
此数据可以验证你的判重对不对
*/
