题解：SP10502 VIDEO - Video game combos

大意

构造一个长度为 \(k\)（\(k\) 是给定的）的串 \(x\)，使得对于 \(∀ 1 \leq i \leq n , s_i\)在 \(x\) 中的出现次数之和最大。

输出这个最大值。

思考

考虑对 \(s_i\)建 AC 自动机，然后 dp。

记 \(dp[i][u]\) 表示为长度为 \(i\) 的字符串，且当前已计算的节点是 Trie 上的编号为 \(u\) 的节点的最大得分。

记 \(tag[k]\) 表示在 Trie 以点 \(k\) 为结尾的字符串的个数。

然后将 \(tag\) 下传。

则转移方程为：

for (int i = 0; i < m; ++i)
		for (int j = 0; j <= cnt; ++j)
			for (int k = 0; k < 3; ++k)
				dp[i + 1][tr[j][k]] = max(dp[i + 1][tr[j][k]], dp[i][j] + tag[tr[j][k]]);

注意这里是以 \(0\) 为 Trie 的根节点。

\(m\) 是读入的 \(k\)。

\(cnt\) 是 Trie 上的节点个数。

答案为：

	for (int i = 0; i <= cnt; ++i)
		ans = max(ans, dp[m][i]);

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

inline int read()
{
	char tr = getchar();
	int x = 0;
	while (tr < '0' || tr > '9')
		tr = getchar();
	while (tr >= '0' && tr <= '9')
		x = x * 10 + tr - '0', tr = getchar();
	return x;
}

#define _ (int)1e5 + 7

int n, m, cnt, tr[_][3], dp[2000][500], fail[_];

int tag[_];

char str[_];

void insert(char *str)
{
	int now = 0;
	int len = strlen(str);
	for (int i = 0; i < len; ++i)
	{
		int p = str[i] - 'A';
		if (!tr[now][p])
			tr[now][p] = ++cnt;
		now = tr[now][p];
	}
	tag[now]++;
}

void get_fail()
{
	queue<int> q;
	for (int i = 0; i < 3; ++i)
		if (tr[0][i])
		{
			fail[tr[0][i]] = 0;
			q.push(tr[0][i]);
		}
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = 0; i < 3; ++i)
			if (tr[u][i])
			{
				fail[tr[u][i]] = tr[fail[u]][i];
				q.push(tr[u][i]);
			}
			else
				tr[u][i] = tr[fail[u]][i];
		tag[u] += tag[fail[u]];
	}
}

signed main()
{
	n = read();
	m = read();
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", str);
		insert(str);
	}
	get_fail();
	int ans = 0;
	for(int i = 0; i < m; ++i)
		for(int j = 1; j <= cnt; ++j) dp[i][j] = INT_MIN;
	for (int i = 0; i < m; ++i)
		for (int j = 0; j <= cnt; ++j)
			for (int k = 0; k < 3; ++k)
				dp[i + 1][tr[j][k]] = max(dp[i + 1][tr[j][k]], dp[i][j] + tag[tr[j][k]]);
	for (int i = 0; i <= cnt; ++i)
		ans = max(ans, dp[m][i]);
	printf("%lld\n", ans);
}

/*
20 1000
CACAACCCCBACA
ACCACAACC
ACAABCACACCACA
A
CCACAACCCCBACA
BCACACCACAAC
CBACAABCACACCA
CCACAACCCC
CACCACAACCCCBA
AABCACACCA
CCCCBACAAB
ACCACAACCCCBA
ACCACAACCCCBAC
C
CAACCCCBACAA
ACAACCCCBACAAB
CCACAACC
ACAABCACACCACAA
CCACAACCCCBACAA
ACAACCCCBACAABC


1795
*/