HDU4057 Rescue the Rabbit

2011大连, AC自动机, DP

　　2011 ACM/ICPC 大连赛区现场赛

　　题意：给定n个模式串及其权值，在主串中可覆盖且每个串只计算一次，求一个长度为L的主串的最大权值和。- 原题链接

　　最开始直接DP求权值和，攻击时某些地方姿势有问题，一直wa= =。后来看网上的报告，用f[i][j][k]表示长度为i目前在节点j且覆盖状态为k的可行性，最后计算所有可行方案的权值和取max。


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
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1024+10, DEF=0x8f8f8f8f;
int n, m, rt, tot, val[maxn];
bool f[2][maxn][maxn];
struct node
{
	int nxt[4], fail, st;
	void Init()
	{
		fail=st=0;
		memset(nxt, 0, sizeof nxt);
		return ;
	}
}tr[maxn];
int getch(char c)
{
	if(c=='A')	return 0;
	if(c=='T')	return 1;
	if(c=='G')	return 2;
	return 3;
}
void Insert(int rt, int k, char *ch)
{
	for(int i=0, len=strlen(ch), cur; i<len; i++)
	{
		cur=getch(ch[i]);
		if(!tr[rt].nxt[cur])
		{
			tr[++tot].Init();
			tr[rt].nxt[cur]=tot;
		}
		rt=tr[rt].nxt[cur];
	}
	tr[rt].st|=(1<<k);
	return ;
}
void Build(int rt)
{
	queue<int> q;
	q.push(rt);
	while(!q.empty())
	{
		int now=q.front(), p=0;
		q.pop();
		for(int i=0; i<4; i++)
		{
			if(!tr[now].nxt[i])	tr[now].nxt[i]=tr[tr[now].fail].nxt[i];
			else
			{
				p=tr[now].nxt[i];
				q.push(p);
				if(now)	tr[p].fail=tr[tr[now].fail].nxt[i];
				tr[p].st|=tr[tr[p].fail].st;
			}
		}
	}
	return ;
}
int Cal(int st)
{
	int cnt=0;
	for(int i=0; i<n; i++) if(st&(1<<i))	cnt+=val[i];
	return cnt;
}
int Work()
{
	memset(f, 0, sizeof f);
	f[0][0][0]=1;
	
	int lim=1<<n, u=0, ans=DEF;
	for(int i=1; i<=m; i++)
	{
		u^=1;
		memset(f[u], 0, sizeof f[u]);
		for(int j=0; j<=tot; j++)
			for(int k=0; k<lim; k++)
				for(int h=0; h<4; h++)
					f[u][tr[j].nxt[h]][k|tr[tr[j].nxt[h]].st]|=f[u^1][j][k];
	}
	for(int i=0; i<=tot; i++)
		for(int j=0; j<lim; j++) if(f[u][i][j])
			ans=max(ans, Cal(j));
	return ans;
}
int main()
{
	while(scanf("%d%d", &n,  &m)!=EOF)
	{
		rt=0, tot=0;
		tr[rt].Init();
		
		char s[maxn];
		for(int i=0; i<n; i++)
		{
			scanf("%s%d", s, &val[i]);
			Insert(rt, i, s);
		}
		Build(rt);
		
		int ans=Work();
		ans<0 ? printf("No Rabbit after 2012!\n") : printf("%d\n", ans);
	}
	return 0;
}