比赛 20120323 评测结果 AAAAAAAAAAWAAWA
题目名称 加利福尼亚旅店 最终得分 86
用户昵称 Czb。 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-03-23 21:16:22
显示代码纯文本
  1. #include<stdio.h>
  2. #include<string.h>
  3. #define max(a,b) a>b?a:b
  4.  
  5. int n,l1,l2,ans,f[100][100];
  6.  
  7. char s[100],c[100];
  8.  
  9. int dp()
  10. {
  11. int i,j,k,t;
  12. k=t=0;
  13. for(i=1;i<=l1;i++)
  14. {
  15. if(s[i-1]=='*')
  16. {
  17. for(j=1;j<i-k;j++)
  18. {
  19. f[i][j]=max(f[i-1][j],f[i][j-1]);
  20. }
  21. for(j=i-k;j<=l2;j++)
  22. {
  23. f[i][j]=max(f[i][j-1],f[i-1][j]);
  24. f[i][j]=max(f[i][j],f[i-1][i-k-1]+j-(i-k-1));
  25. }
  26. k++;
  27. }
  28. else
  29. {
  30. for(j=1;j<=l2;j++)
  31. {
  32. if(s[i-1]=='?'||s[i-1]==c[j-1])
  33. f[i][j]=f[i-1][j-1]+1;
  34. else
  35. {
  36. f[i][j]=max(f[t][j-1],f[i][j-1]);
  37. if(f[t][j]<=i-k)
  38. f[i][j]=max(f[i][j],f[t][j]);
  39. }
  40. }
  41. t=i;
  42. }
  43. }
  44. if(l1-k>l2)return -1;
  45. return f[l1][l2];
  46. }
  47.  
  48. int main()
  49. {
  50. freopen("hotela.in","r",stdin);
  51. freopen("hotela.out","w",stdout);
  52. while(scanf("%s\n",s)==1)
  53. {
  54. ans=0;
  55. scanf("%d\n",&n);
  56. l1=strlen(s);
  57. while(n--)
  58. {
  59. scanf("%s\n",c);
  60. l2=strlen(c);
  61. memset(f,0,sizeof(f));
  62. if(dp()==l2)
  63. ans++;
  64. }
  65. printf("%d\n",ans);
  66. }
  67. return 0;
  68. }