P3041 视频游戏

P3041 [USACO12JAN]视频游戏的连击Video Game Combos

可以想到，用 $dp(i,j)$ 代表输入字符串长度为 $i$ ，匹配到节点 $j$ 时可以达到的最大分数。

我们有 $dp(i,ch(j,k))=\min\lbrace dp(i-1,j)\rbrace$ 。

注意初始化为负无穷。

#include <bits/stdc++.h>
#define MAXN 1005
#define MAXM 27
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
char s[MAXN];
int n,m,tot;
namespace AC_Automation{
	int trie[MAXN][MAXM],fail[MAXN*MAXM],cnt[MAXN*MAXM];
	void Insert(char *s){
		int len=strlen(s),root=0;
		for (int i=0;i<len;++i){
			int c=s[i]-'A';
			if (!trie[root][c]) trie[root][c]=++tot;
			root=trie[root][c];
		}
		cnt[root]++;
	}
	void BuildFail(){
		queue<int>Q;
		for (int i=0;i<3;++i){
			if (trie[0][i]) Q.push(trie[0][i]);
		}
		while (Q.size()){
			int now=Q.front();Q.pop();
			cnt[now]+=cnt[fail[now]];
			for (int i=0;i<3;++i){
				int &child=trie[now][i];
				if (child){
					fail[child]=trie[fail[now]][i];
					Q.push(child);
				}
				else {
					child=trie[fail[now]][i];
				}
			}
		}
	}
	int dp[MAXN][MAXN*MAXM];
	void DP(int id){
		for (int i=0;i<=tot;++i){
			for (int j=0;j<3;++j){
				int v=trie[i][j];
				dp[id][v]=max(dp[id][v],dp[id-1][i]+cnt[v]);
			}
		}
	}
}
using namespace AC_Automation;
int main(){
	n=read(),m=read();
	for (int i=1;i<=n;++i){
		scanf("%s",s);
		Insert(s);
	}
	BuildFail();
	memset(dp,~0x3f,sizeof(dp));
	for (int i=0;i<=m;++i){
		dp[i][0]=0;
	}
	for (int i=1;i<=m;++i){
		DP(i);
	}
	int ans=0;
	for (int i=0;i<=tot;++i){
		ans=max(ans,dp[m][i]);
	}
	printf("%d\n",ans);
}