传送门

给出 n n n个字符串,构造一个长度为 k k k的字符串

字符串的贡献定义为所有子串的贡献和,子串如果等于给出的字符串贡献为1,否则为0

求构造字符串的最大价值

n < = 20 , ∣ s ∣ < = 15 , k < = 1000 n<=20,|s|<=15,k<=1000 n<=20,∣s∣<=15,k<=1000

---

考虑状压前 15 15 15个单词,复杂度为 3 15 3^{15} 315,无法储存

然后就不知道怎么做了考虑 A C AC AC自动机

定义 f [ i ] [ j ] f[i][j] f[i][j]为字符串长度为 i i i,目前在 t i r e tire tire树上的 j j j节点

那么每次枚举这一次填充的 26 26 26个字母 q q q

f [ i + 1 ] [ z i [ j ] [ q ] ] = f [ i ] [ j ] + v a l f[i+1][zi[j][q]]=f[i][j]+val f[i+1][zi[j][q]]=f[i][j]+val

那么 v a l val val等于多少呢 ? ? ?? ??

v a l val val等于以 q q q结尾的所有单词串,不难发现建立 t i r e tire tire图就不用跳 f a i l fail fail快速转移

非常套路的题,做过就非常简单

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1009;
int zi[maxn][4],fail[maxn],last[maxn],id,n,m,ans,f[maxn][maxn],val[maxn];
char a[maxn];
void insert(char a[] )
{
	int n = strlen( a+1 ), now = 0;
	for(int i=1;i<=n;i++)
	{
		if( !zi[now][a[i]-'A'] )	zi[now][a[i]-'A'] = ++id;
		now = zi[now][a[i]-'A']; 
	}
	val[now]++;
}
void get_fail()
{
	queue<int>q;
	for(int i=0;i<=2;i++)
		if( zi[0][i] )	q.push( zi[0][i] );
	while( !q.empty() )
	{
		int u = q.front(); q.pop();
		val[u] += val[fail[u]];
		for(int i=0;i<=2;i++)
		{
			if( zi[u][i] )
				fail[zi[u][i]] = zi[fail[u]][i],q.push( zi[u][i] );
			else	zi[u][i] = zi[fail[u]][i];
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		cin >> ( a+1 ),insert( a );
	get_fail();
	int ans = 0;
	memset( f,-1,sizeof f);
	f[0][0] = 0;
	for(int i=0;i<m;i++)
	for(int j=0;j<=id;j++)
	for(int q=0;q<=2;q++)
	{
		if( f[i][j]==-1 )	continue;
		int nxt = zi[j][q];
		f[i+1][nxt] = max( f[i+1][nxt],f[i][j]+val[nxt] );
		ans = max( ans,f[i+1][nxt] );
	}
	cout << ans;
}