AK-dream

【题目描述】
贝西在玩一款游戏,该游戏只有三个技能键 $\texttt{A,B,C}$ 可用,但这些键可用形成N种($1 \le N\le 20$)特定的组合技。第$i$个组合技用一个长度为$1$到$15$的字符串$S_i$表示。

当贝西输入的一个字符序列和一个组合技匹配的时候,他将获得$1$分。特殊的,他输入的一个字符序列有可能同时和若干个组合技匹配,比如$N=3$时,3种组合技分别为”$\texttt{ABA}$”, “$\texttt{CB}$”, 和”$\texttt{ABACB}$”,若贝西输入”$\texttt{ABACB}$”,他将获得$3$分。

若贝西输入恰好$K$ ($1 \le K \le 1000)$个字符,他最多能获得多少分?

【输入格式】
第一行包含两个整数$N$和$K$

接下来$N+1$行,第$i+1$行包含字符串$S_i$

【输出格式】
输出最大获得多少分。

题解


发现是要你构造一个长串去匹配若干给出的串 所以自然想到AC自动机

设$\operatorname{f}(x)$为 x到根的fail链上的 打了结束标记的点个数。

假设把那个长串给你了 那匹配套路无非就是在AC自动机上跳 每跳到一个点x 分数就加上$\operatorname{f}(x)$。(如果不懂请去学刁一下AC自动机)

那反正这$N$个串是不会变了 所以建好AC自动机之后把每个点x的$\operatorname{f}(x)$预处理出来

然后显然是个DP 设 $dp[i][j]$ 表示 枚举到答案串的第$i$位,最后一位在AC自动机的$j$号节点上

转移方程就是枚举$i,j$ 枚举$k\in [0,25]$表示枚举到的字母 $dp[i+1][j] = max(dp[i+1][son[j][k]], dp[i][j]+f(son[j][k]))$

不需要特判什么$son[j][k]=0$之类的 答案串一直在节点0打转也是无所谓的 不影响DP

影响DP的是 有些状态$dp[i][j]$是无法到达的 所以我们先把整个dp数组设为$-1$ 然后让$dp[0][0]=0$ 如果枚举到$i,j\ \ dp[i][j]=-1$那就表示这个状态无法到达 要跳过

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
#include <bits/stdc++.h>
using namespace std;

int n, m;
char s[30];
int ch[10005][30], fail[10005], val[10005], tot;
int dp[1005][1005];
bool tag[100005];

inline void insert(char *str, int l) {
int x = 0;
for (int i = 1; i <= l; i++) {
if (!ch[x][str[i] - 'A']) {
ch[x][str[i] - 'A'] = ++tot;
}
x = ch[x][str[i] - 'A'];
}
tag[x] = 1;
}

queue<int> q;

inline void getfail() {
for (int i = 0; i < 26; i++) if (ch[0][i]) q.push(ch[0][i]);
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = 0; i < 26; i++) {
if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
else ch[x][i] = ch[fail[x]][i];
}
}
}

inline void calc() {
for (int i = 0; i <= tot; i++) {
for (int j = i; j; j = fail[j]) {
if (tag[j]) val[i]++;
}
}
}

inline void DP() {
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j <= tot; j++) {
if (dp[i][j] == -1) continue;
for (int k = 0; k < 26; k++) {
dp[i+1][ch[j][k]] = max(dp[i+1][ch[j][k]], dp[i][j] + val[ch[j][k]]);
}
}
}
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", s+1);
insert(s, strlen(s+1));
}
getfail();
calc();
DP();
int ans = 0;
for (int i = 0; i <= tot; i++) {
ans = max(ans, dp[m][i]);
}
printf("%d\n", ans);
return 0;
}

 评论