欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1966

题意概括

　　现在有一些串和一个病毒模板。让你统计非病毒串的总数。串个数<=500。

　　串由'A' 'C' 'G' 'T'构成，长度<=500。

　　病毒模板（长度<=1000）较为复杂，由'A' 'C' 'G' 'T' '*' '?'组成。其中'A' 'C' 'G' 'T'没有特异功能。但是'*' 和 '?'有特意功能：

　　'*'：在这里可以填充任意长度的任意串（由A,C,G,T组成，长度可以为0）。

　　'?'：在这里能且仅能填一个字母，这个字母在A,C,G,T中选。

　　如果病毒模板通过在'.'和'?'中填字母可以做到和某一个串相同，那么这个串就是病毒串。反之就是非病毒串。

题解

　　我们发现连续的'*'是没用的可以压成一个'*'，花几行代码压掉。

　　然后对于每一个串，我们跑一个二维的dp。

　　用f[i][j]表示从病毒串的第i位开始，当前串的第j位开始，能否得到匹配。

　　那么有3种转移：

　　1. 当前模板位为‘*’，那么我们可以考虑结束'*'或者继续匹配当前串，故f[i][j]=f[i][j+1] or f[i+1][j]

　　2. 当前模板位为'?'，那么我们只能做到和当前字符匹配，故f[i][j]=f[i+1][j+1]

　　3. 当前模板位为字符，那么我判断一下和当前串位是否相同，如果不同那么f[i][j]=0，否则f[i][j]=f[i+1][j+1]

　　注意特殊情况：

　　最后的时候，模板串还有'*',但是当前串已经匹配完的情况要注意一下。

　　dp主体写在dfs里面。

代码

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <cstdlib>

using namespace std;

const int M=1005,N=505;

int t,n,m,ans=0,f[M][N];

char str[M],ch[N];

void recreate(){

	int m_=1;

	for (int i=2;i<=m;i++)

		if (!(str[i]==str[i-1]&&str[i]=='*'))

			str[++m_]=str[i];

	m=m_;

}

bool dfs(int x,int y){

	if (~f[x][y])

		return f[x][y];

	if (x>m&&y>n)

		return f[x][y]=1;

	if (str[x]=='*'&&y>n)

		return f[x][y]=dfs(x+1,y);

	if (x>m||y>n)

		return f[x][y]=0;

	if (str[x]=='?')

		return f[x][y]=dfs(x+1,y+1);

	if (str[x]=='*')

		return f[x][y]=dfs(x,y+1)||dfs(x+1,y);

	if (str[x]!=ch[y])

		return f[x][y]=0;

	return f[x][y]=dfs(x+1,y+1);

}

int main(){

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

	m=strlen(str+1);

	recreate();

	scanf("%d",&t);

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

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

		n=strlen(ch+1);

		memset(f,-1,sizeof f);

		if (!dfs(1,1))

			ans++;

	}

	printf("%d",ans);

	return 0;

}

巴特西

BZOJ1966 [Ahoi2005]VIRUS 病毒检测动态规划

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1966

题意概括

题解

代码

最新文章

热门文章

巴特西

BZOJ1966 [Ahoi2005]VIRUS 病毒检测 动态规划

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1966

题意概括

题解

代码

最新文章

热门文章

BZOJ1966 [Ahoi2005]VIRUS 病毒检测动态规划