比赛 |
20120323 |
评测结果 |
AAAAAAAAAAAAAAA |
题目名称 |
加利福尼亚旅店 |
最终得分 |
100 |
用户昵称 |
恢复用户700 |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2012-03-23 21:39:52 |
显示代码纯文本
(*
Problem : Hotel
Author : whitetooth
Start Time : 2012-3-23 19:21
Finish Time : 2012-3-23 19:49
Result :
Method : Dynamic Programming
*)
Program Hotel;
Const
maxn=50+5;
Var
f,vis :array[0..maxn,0..maxn] of boolean;
s1,s2 :string;
n,i :longint;
ans :longint;
Procedure Dfs(p,q,l1,l2:longint);
Begin
if vis[p,q] then exit;
vis[p,q]:=true;
if (p>l1)and(q>l2) then
begin
f[p,q]:=true;
exit;
end;
if (p>l1)and(q<=l2) then
begin
f[p,q]:=false;
exit;
end;
if (p<=l1)and(q>l2) then
begin
if s1[p]='*' then
begin
dfs(p+1,q,l1,l2);
f[p,q]:=f[p+1,q];
end
else f[p,q]:=false;
exit;
end;
if s1[p]='?' then
begin
dfs(p+1,q+1,l1,l2);
f[p,q]:=f[p+1,q+1];
exit;
end;
if s1[p]='*' then
begin
dfs(p,q+1,l1,l2);
dfs(p+1,q,l1,l2);
f[p,q]:=f[p,q+1] or f[p+1,q];
exit;
end;
if s1[p]<>s2[q] then f[p,q]:=false
else
begin
dfs(p+1,q+1,l1,l2);
f[p,q]:=f[p+1,q+1];
end;
End;
Procedure Main;
Begin
ans:=0;
readln(s1);
readln(n);
for i:=1 to n do
begin
readln(s2);
fillchar(vis,sizeof(vis),false);
dfs(1,1,length(s1),length(s2));
if f[1,1] then inc(ans);
end;
writeln(ans);
End;
Begin
Assign(input,'hotela.in'); reset(input);
Assign(output,'hotela.out'); rewrite(output);
While not seekeof do main;
Close(input); close(output);
End.