链接：https://www.nowcoder.com/acm/contest/72/B
来源：牛客网
题目描述
小H在击败怪兽后，被一个密码锁挡住了去路
密码锁由N个转盘组成，编号为1~N，每个转盘有M个位置，每个位置上要么有一个小写字母，要么没有任何字符。一个密码能被转盘表示出，当且仅当指定每个转盘上面的某一个位置，然后将这些位置按照所属的转盘编号顺次连接(空位置直接忽略)，可以得到这个密码
小H并没有得到任何线索，因此只能猜，她一共猜了Q次，但并不知道自己猜的密码能否被表示出来，于是她向你求助
密码锁由N个转盘组成，编号为1~N，每个转盘有M个位置，每个位置上要么有一个小写字母，要么没有任何字符。一个密码能被转盘表示出，当且仅当指定每个转盘上面的某一个位置，然后将这些位置按照所属的转盘编号顺次连接(空位置直接忽略)，可以得到这个密码
小H并没有得到任何线索，因此只能猜，她一共猜了Q次，但并不知道自己猜的密码能否被表示出来，于是她向你求助
输入描述:
第1行，三个整数N,M,Q
第2~N+1行，每行一个长度为M的字符串，依次表示每个转盘上的字符
第N+2~N+Q+1行，每行一个长度不超过10000的字符串，表示小H猜的密码
2≤N,Q≤300，2≤M≤27，同一个转盘上每种字符最多出现一次
输出描述:
输出Q行，每行都是YES或NO，依次表示小H猜的每个字符串能否被表示出
输入例子:
3 2 3
a#
ab
bc
aa
bb
ba
输出例子:
NO
YES
NO
-->
示例1
输入
3 2 3
a#
ab
bc
aa
bb
ba
输出
NO
YES
NO
备注:
#表示空字符 分析：
用贪心确定每个密码盘选哪个字符是错误的
递归肯定超时，剪枝都补救不了
所以这题看起来字符串模拟的题，居然要用dp写。。。
考虑DP，设dp[i][j]表示前i个密码盘，有j个选了某个小写字母的方案 时间复杂度O(N^2Q)
则决策只有当前密码盘选择空字符或者小写字母两种
用桶记录每个位置有哪些可用字母，询问串过长直接输出NO
重点：初始化+bool传递
所以第二位选0个的项都设为1
看别人代码，学了一招，传递可行性用&1，很骚
#include<bits/stdc++.h>
using namespace std;
#define maxn 10000
typedef long long ll;
#define inf 2147483647
#define ri register int int n,m,q;
int str[][];
int dp[][];
char ss[maxn],s[maxn]; int main()
{
// freopen("test.txt","r",stdin);
// freopen("outout.txt","w",stdout);
cin>>n>>m>>q;
for(int i=; i<=n; i++)
{
scanf("%s",ss);
for(int j=; j<strlen(ss); j++)
{
if(ss[j]=='#')
str[i][]=;
else str[i][ss[j]-'a'+]=;
}
}
while(q--)
{
memset(dp,,sizeof(dp));
scanf("%s",s+);
int len=strlen(s+);
if(len>n){
cout<<"NO"<<endl;
continue;
}
for(int i=; i<=n; i++)
dp[i][]=;
for(int i=; i<=n; i++)
for(int j=; j<=i; j++)
{
if(str[i][s[j]-'a'+])
dp[i][j]=dp[i-][j-]&;
if(str[i][]&&!dp[i][j])
dp[i][j]=dp[i-][j]&;
}
if(dp[n][len])
cout<<"YES";
else cout<<"NO";
cout<<endl;
}
return ;
}