[数据结构与算法] AC自动机+动态规划 P3041 [USACO12JAN]Video Game G

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> AC自动机+动态规划 P3041 [USACO12JAN]Video Game G -> 正文阅读

[数据结构与算法]AC自动机+动态规划 P3041 [USACO12JAN]Video Game G

题目链接

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
namespace AC
{
	int tr[N][5],tot;
	int exist[N],fail[N];
	void insert(char *s)
	{
		int p=0;
		for(int i=1;s[i];i++)
		{
			if(!tr[p][s[i]-'A']) tr[p][s[i]-'A']=++tot;
			p=tr[p][s[i]-'A'];
		}
		exist[p]++;
	}
	queue<int>q;
	void build()
	{
		for(int i=0;i<3;i++)if(tr[0][i])q.push(tr[0][i]);
		while(q.size())
		{
			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];
			}
		}
	}
	int query(int u,int res)
	{
		while(u) res+=exist[u],u=fail[u];
		return res;
	}
}
int n,k;
char s[N];
int dp[N][N],vis[N][N];
void solve()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		AC::insert(s);
	}
//	cout<<"?"<<endl;
	AC::build();
//	cout<<"?"<<endl;
	vis[0][0]=1;
	for(int i=0;i<k;i++)
	{
		for(int j=0;j<=AC::tot;j++)
		{
			if(!vis[i][j]) continue;
			for(int k=0;k<3;k++)
			{
				dp[i+1][AC::tr[j][k]]=max(dp[i+1][AC::tr[j][k]],AC::query(AC::tr[j][k],dp[i][j]));
				vis[i+1][AC::tr[j][k]]=1;
			}
		}
	}
	int ans=0;
	for(int i=0;i<=AC::tot;i++) ans=max(ans,dp[k][i]);
	printf("%d\n",ans);
}
signed main()
{
	int T=1;
	for(int i=1;i<=T;i++)
	{
		solve();
	}
	return 0;
}