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