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