比赛 |
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;
}