Wannafly挑战赛10

B 小H和密码

链接：https://www.nowcoder.com/acm/contest/72/B
来源：牛客网

题目描述

 小H在击败怪兽后，被一个密码锁挡住了去路
  密码锁由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，同一个转盘上每种字符最多出现一次

分析

 贪心明显是不行的，因为当前字母可以被选择也可以不被选择，先想到的是深搜，可以选或者不选（如果有空格的话）但是复杂度太高所以只能dp了(具体分析看代码注释）

#include <bits/stdc++.h>

using namespace std;
const int maxn = 300+10;
bool Turn[maxn][30];
const int maxn2 = 10000+100;
char s[maxn2];
int len;
int N,M,Q;
bool dp[maxn][maxn];
int main()
{

    cin>>N>>M>>Q;
    for(int i = 0; i < N; ++i)
    {
        scanf("%s",s);
        for(int j = 0; j < M; ++j)
        {
            if(s[j]=='#')//如果有空格特别标注
                Turn[i][26] = 1;
            else
                Turn[i][s[j]-'a'] = 1;
        }
    }
    while(Q--)
    {
        scanf("%s",s);
        len = strlen(s);
        bool yes = true;
        if(len>N)
            yes = false;
        else {
            memset(dp,0,sizeof(dp));//对于每一个字符串都要进行dp
            for(int i = 0;i < N; ++i)
            {
                for(int j = 0;j < len; ++j)
                {
                    if(j==0&&Turn[i][s[j]-'a']) dp[i][j] = true;//如果是第一个字符，可以直接选择
                    if(i&&dp[i-1][j]&&Turn[i][26]) dp[i][j] = true;//如果有空格，则可以不选
                    if(j&&i&&dp[i-1][j-1]&&Turn[i][s[j]-'a'])  dp[i][j] = true;//如果不是第一个字符，就需要前面的所有的字符都已经找到
                }
            }
            if(!dp[N-1][len-1])
                yes = false;
        }
        if(yes)
            printf("YES\n");
        else
            printf("NO\n");
        //cout<<"NO"<<endl;
    }
    return 0;
}