比赛 20120323 评测结果 AAAAAAAAAAWAAWA
题目名称 加利福尼亚旅店 最终得分 86
用户昵称 Czb。 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-03-23 21:16:22
显示代码纯文本
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b

int n,l1,l2,ans,f[100][100];

char s[100],c[100];

int dp()
{
	int i,j,k,t;
	k=t=0;
	for(i=1;i<=l1;i++)
	{
		if(s[i-1]=='*')
		{
			for(j=1;j<i-k;j++)
			{
				f[i][j]=max(f[i-1][j],f[i][j-1]);
			}
			for(j=i-k;j<=l2;j++)
			{
				f[i][j]=max(f[i][j-1],f[i-1][j]);
				f[i][j]=max(f[i][j],f[i-1][i-k-1]+j-(i-k-1));
			}
			k++;
		}
		else
		{
			for(j=1;j<=l2;j++)
			{
				if(s[i-1]=='?'||s[i-1]==c[j-1])
					f[i][j]=f[i-1][j-1]+1;
				else
				{
					f[i][j]=max(f[t][j-1],f[i][j-1]);
					if(f[t][j]<=i-k)
						f[i][j]=max(f[i][j],f[t][j]);
				}
			}
			t=i;
		}
	}
	if(l1-k>l2)return -1;
	return f[l1][l2];
}

int main()
{
	freopen("hotela.in","r",stdin);
	freopen("hotela.out","w",stdout);
	while(scanf("%s\n",s)==1)
	{
		ans=0;
		scanf("%d\n",&n);
		l1=strlen(s);
		while(n--)
		{
			scanf("%s\n",c);
			l2=strlen(c);
			memset(f,0,sizeof(f));
			if(dp()==l2)
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}