USACO2007FEB SILVER 牛的词典

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Sep 05 13:05:13 CST 2018

In Category: NoCategory

Description：

给 $m$ 个词，每个词最长不超过 $25$ ，给一个串，问最少去掉几个字母可以使得这个词变成一些给出的词的排列。

$1\le m \le 600,2\le l \le 300$

Solution：

预处理 $g[i][j]$ 表示串的第 $i$ 位开始匹配第 $j$ 个串最少需要删去多少个字符。由于串只有 $300$ 长，所以可以暴力匹配， $O(n^2m)$ 。

倒着 $DP$ ， $f[i]$ 表示从 $i$ 开始匹配完最少删去多少字符。

转移为： $f[i]=\min(f[i+len[j]+g[i][j]]+g[i][j])$

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXM 610

#define MAXN 310

inline char getc()

{

	register char c = getchar();

	while(!islower(c))c = getchar();

	return c;

}

char str[MAXN];

char ch[MAXM][30];

int g[MAXN][MAXM];

int l[MAXM];

int f[MAXN];

#define INF 0x3f3f3f3f

int main()

{freopen("4.in","r",stdin);

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

	for(int i = 1;i <= n;++i)str[i] = getc();

	for(int i = 1;i <= m;++i)scanf("%s",ch[i] + 1);

	for(int i = 1;i <= m;++i)l[i] = strlen(ch[i] + 1);

	memset(f,0x3f,sizeof(f));

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

	{

		for(int j = 1;j <= m;++j)

		{

			int l1 = i,l2 = 1;

			g[i][j] = 0;

			while(l1 <= n && l2 <= l[j])

			{

				if(str[l1] == ch[j][l2])

				{

					++l1;++l2;

				}

				else

				{

					++l1;++g[i][j];

				}

			}

			if(l2 != l[j] + 1)g[i][j] = INF;

		}

	}

	f[n + 1] = 0;

	for(int i = n;i >= 1;--i)

	{

		f[i] = f[i + 1] + 1;

		for(int j = 1;j <= m;++j)

			if(g[i][j] != INF)

				f[i] = min(f[i],f[i + l[j] + g[i][j]] + g[i][j]);

	}

	cout << f[1] << endl;

	return 0;

}

In tag: DP-DP

wjh15101051