Steven_MengのBlog

P3041 [USACO12JAN]视频游戏的连击Video Game Combos

可以想到,用 $dp(i,j)$ 代表输入字符串长度为 $i$ ,匹配到节点 $j$ 时可以达到的最大分数。

我们有 $dp(i,ch(j,k))=\min\lbrace dp(i-1,j)\rbrace$。

注意初始化为负无穷。

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
#include <bits/stdc++.h>
#define MAXN 1005
#define MAXM 27
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
return x*f;
}
char s[MAXN];
int n,m,tot;
namespace AC_Automation{
int trie[MAXN][MAXM],fail[MAXN*MAXM],cnt[MAXN*MAXM];
void Insert(char *s){
int len=strlen(s),root=0;
for (int i=0;i<len;++i){
int c=s[i]-'A';
if (!trie[root][c]) trie[root][c]=++tot;
root=trie[root][c];
}
cnt[root]++;
}
void BuildFail(){
queue<int>Q;
for (int i=0;i<3;++i){
if (trie[0][i]) Q.push(trie[0][i]);
}
while (Q.size()){
int now=Q.front();Q.pop();
cnt[now]+=cnt[fail[now]];
for (int i=0;i<3;++i){
int &child=trie[now][i];
if (child){
fail[child]=trie[fail[now]][i];
Q.push(child);
}
else {
child=trie[fail[now]][i];
}
}
}
}
int dp[MAXN][MAXN*MAXM];
void DP(int id){
for (int i=0;i<=tot;++i){
for (int j=0;j<3;++j){
int v=trie[i][j];
dp[id][v]=max(dp[id][v],dp[id-1][i]+cnt[v]);
}
}
}
}
using namespace AC_Automation;
int main(){
n=read(),m=read();
for (int i=1;i<=n;++i){
scanf("%s",s);
Insert(s);
}
BuildFail();
memset(dp,~0x3f,sizeof(dp));
for (int i=0;i<=m;++i){
dp[i][0]=0;
}
for (int i=1;i<=m;++i){
DP(i);
}
int ans=0;
for (int i=0;i<=tot;++i){
ans=max(ans,dp[m][i]);
}
printf("%d\n",ans);
}

 评论