USACO2012JAN Video Game

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Tue Oct 23 17:07:34 CST 2018

In Category: NoCategory

Description：

给出 $n$ 个 $ABC$ 串和 $k$ ，现要求生成一个长 $k$ 的字符串 $S$ ，问 $S$ 与 $word[1\dots n]$ 的最大匹配数。

$1\leqslant n\leqslant 15,1\leqslant l\leqslant20,1\leqslant k\leqslant 1000$

Solution：

往后面加字符，也就是在 $AC$ 自动机上走一步，新产生的匹配一定是一个后缀，于是先把所有 $fail$ 链累加起来，就得到了从父亲走到这里获得的新的价值，然后记搜就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 21

#define MAXL 17

char c[MAXL];

#define MAXM 1010

struct node

{

	int tr[3];

	int fail;

	int cnt;

	node(){cnt = 0;}

}t[MAXN * MAXL];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void insert(char c[])

{

	int l = strlen(c + 1);

	int cur = root;

	for(int i = 1;i <= l;++i)

	{

		if(t[cur].tr[c[i] - 'A'] == 0)

			t[cur].tr[c[i] - 'A'] = newnode();

		cur = t[cur].tr[c[i] - 'A'];

	}

	++t[cur].cnt;

	return;

}

void make_fail()

{

	queue<int> q;

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

		if(t[root].tr[i] != 0)

			q.push(t[root].tr[i]);

	while(!q.empty())

	{

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

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

		{

			if(t[k].tr[i] != 0)

			{

				t[t[k].tr[i]].fail = t[t[k].fail].tr[i];

				q.push(t[k].tr[i]);

			}

			else t[k].tr[i] = t[t[k].fail].tr[i];

		}

		t[k].cnt += t[t[k].fail].cnt;

	}

	return;

}

int f[MAXN * MAXL][MAXM];

int dp(int k,int l)

{

	if(f[k][l] != -1)return f[k][l];

	if(l == 0)return (f[k][l] = t[k].cnt);

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

	{

		f[k][l] = max(f[k][l],dp(t[k].tr[i],l - 1));

	}

	f[k][l] += t[k].cnt;

	return f[k][l];

}

int main()

{

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

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

	{

		scanf("%s",c + 1);

		insert(c);

	}

	make_fail();

	memset(f,-1,sizeof(f));

	cout << dp(root,m) << endl;

	return 0;

}

In tag: 字符串-AC自动机 DP-记忆化搜索

wjh15101051