本题是一道 AC 自动机上的 dp。
首先不难想到状态定义 f(i,j) 表示仅考虑前 i 个位置，第 i 个字符是 j 的分数，但无法转移，所以考虑将 j 这一维转化为表示 AC 自动机上的点。
再定义 val(i) 表示以 i 结尾的所有技能种数，则转移方程为 f(i,j)=max(f(i,j),f(i-1,father(j)+val(j))。
现在问题转化为求 val。求 val 的话在求 AC 自动机的 fail 指针那部分里来求，转移式为 val(i)=end(i)+val(fail(i))，其中 end(i) 表示以 i 结尾的字符串数。
代码：
#include <bits/stdc++.h>
using namespace std;
const int Pig = 1e3 + 10;
int f[Pig][Pig];
struct ac_automaton{
int tr[Pig][4], end_[Pig], fail[Pig], cnt = 0, val[Pig];
ac_automaton() {
memset(tr, 0, sizeof(tr));
memset(end_, 0, sizeof(end_));
memset(val, 0, sizeof(val));
memset(fail, 0, sizeof(fail));
}
void insert(string n) {
int p = 0;
for (auto v : n) {
if (!tr[p][v - 'A'])
tr[p][v - 'A'] = ++cnt;
p = tr[p][v - 'A'];
}
end_[p]++;
}
void build() {
queue<int> q;
for (int i = 0; i < 3; i++) {
if (tr[0][i])
q.emplace(tr[0][i]);
}
while (!q.empty()) {
int p = q.front();
q.pop();
for (int i = 0; i < 3; i++) {
if (tr[p][i]) {
fail[tr[p][i]] = tr[fail[p]][i];
q.push(tr[p][i]);
} else {
tr[p][i] = tr[fail[p]][i];
}
}
val[p] = end_[p] + val[fail[p]];
}
}
};
ac_automaton tr;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
string cur;
cin >> cur;
tr.insert(cur);
}
tr.build();
memset(f, -0x3f3f3f3f, sizeof(f));
for (int i = 0; i <= k; i++)
f[i][0] = 0;
int ans = 0;
for (int i = 1; i <= k; i++) {
for (int j = 0; j <= tr.cnt; j++) {
for (int l = 0; l < 3; l++) {
f[i][tr.tr[j][l]] = max(f[i][tr.tr[j][l]], f[i - 1][j] + tr.val[tr.tr[j][l]]);
}
}
}
for (int i = 0; i <= tr.cnt; i++)
ans = max(ans, f[k][i]);
cout << ans;
return 0;
}