【题解】[USACO12JAN]Video Game G

第一道\(AC\)自动机\(+DP.\)

首先，一个自动机上\(DP\)的套路是设\(dp[i][j]\)表示长度为\(i\)匹配到\(j\)节点的最优得分。

那么，由于我们已经建好了\(Trie\)图，我们就应该提前把走到节点\(j\)的所有连击操作处理出来。

有一条显然结论：如果在\(fail\)树上经过了这个串结尾节点中子树中的任意一点，则这次匹配一定会包含这个串。

换句话说，我们在对每一个节点更新\(fail\)的时候，其分值应该直接把其\(fail\)的分值加上。

于是我们进行\(dp.\)

首先初始值都是\(-inf,\)但对于匹配节点在根的情况应该是\(0.\)

至于为什么\(dp[0][*]\)不能赋值为\(0,\)是因为根本不可能存在这种状态。匹配长度为\(0\)不可能匹配到其他节点。

但初始时，不管哪一个节点和\(0\)匹配，其一定不会有任何分数。根节点本身是一个空节点。

解决初始值问题，我们可以进行\(dp.\)

枚举长度，枚举节点，再枚举字符。对于一个状态，我们应该取所有能到达这个状态的\(dp\)值的\(\max.\)因为我只能输入\(k\)个字符。

剩下的就是模板了。

#include<bits/stdc++.h>

using namespace std;

int dp[5000][2000];

const int MAXN=4000;

int pos[MAXN],cnt[MAXN];

int tot,n;

char st[MAXN];

struct Tree{

	int ch[3],fail;

}T[MAXN];

vector<int>to[MAXN];

int num[MAXN];

int insert(char *str,int len){

	int u=0;

	for(int i=0;i<len;++i){

		int x=str[i]-'A';

		if(!T[u].ch[x])T[u].ch[x]=++tot;

		u=T[u].ch[x];

	}

	num[u]++;return u;

}

void bfs(){

	queue<int>q;

	for(int i=0;i<3;++i){

		if(T[0].ch[i]){

			int v=T[0].ch[i];

			T[v].fail=0;

			q.push(v);

		}

	}

	while(!q.empty()){

		int u=q.front();q.pop();

		for(int i=0;i<3;++i){

			if(T[u].ch[i]){

				int v=T[u].ch[i];

				T[v].fail=T[T[u].fail].ch[i];

				q.push(v);

			}

			else T[u].ch[i]=T[T[u].fail].ch[i];

		}

		to[T[u].fail].push_back(u);

		num[u]+=num[T[u].fail];

	}

}

int K;

int main(){

	scanf("%d%d",&n,&K);

	for(int i=1;i<=n;++i){

		scanf("%s",st);

		int L=strlen(st);

		pos[i]=insert(st,L);

	}

	bfs();

	memset(dp,128,sizeof(dp));

	for(int i=0;i<=K;++i)dp[i][0]=0;

	for(int i=1;i<=K;++i){

		for(int j=0;j<=tot;++j){

			for(int k=0;k<3;++k){

				dp[i][T[j].ch[k]]=max(dp[i][T[j].ch[k]],dp[i-1][j]+num[T[j].ch[k]]);

			}

		}

	}

	int ans=0;

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

	printf("%d\n",ans);

	return 0;

}

巴特西

【题解】[USACO12JAN]Video Game G

最新文章

热门文章