F - DFS枚举 CSU - 2087: Tragedy Words-白红宇

F - DFS枚举 CSU - 2087: Tragedy Words

阅读量：5922 次

发布时间：2019-06-19

本文共 2494 字，大约阅读时间需要 8 分钟。

As is known to all, Wells doesn't have a good command of English. As a result, some unfamiliar words, which may cause sadness of Wells, is called tragedy words. In more detail, a word will be defined as a tragedy word, if and only if when it satisfies all following conditions.

First, it only contain uppercase letter.

Second, it doesn't contain three consecutive vowel(AEIOU) or three consecutive consonant(the other 21 letter).

And last of all, it should contain at least one special tragedy letter 'L'.

Now, you are given a word, which consists of uppercase letter or underline, and you are allow to fill each underline with one uppercase letter. And in order to make fun of Wells, you want to know how many tragedy words you can make in this way.

Input

For each test, only contains a line of one word, which consists of uppercase letter and underline(’_’).

The total length of each word will not exceed 100, and the number of underline(’_’) will not exceed 10.

Output

For each test, print one line, which contains a integer as the total amount of tragedy words you can make.

Notice: the number may be very large and may exceed the 32-bits unsigned integer.

Sample Input
V__KV_K
Sample Output
100
Hint

The vowel means 'A','E','I','O','U'

The consonant means the other 21 letter.

The special tragedy letter 'L' still belongs to consonant.

Of course, the letter here means English letters, not other language letters.

题意：输入时只包含大写字母和下划线的字符串，要在下划线的位置填入大写字母，要求填完后字符串满足：1.没有3个辅音或元音字母相连，至少有一个L。输出方案数

思路：可以把字母分成两种元音（5）、辅音（21），DFS一个下划线一个下划线地填上元音或辅音，如果填入元音可以则结果*5，如果填入辅音可以则结果*21，中间要特殊处理L

也可以分成三种元音（5）、辅音（20）、L，思路和上面差不多，就L的处理稍有不同

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              typedef long long LL;using namespace std;const int maxn=111;char str[maxn];int ma[maxn];int a[3]={1,20,5};int N;LL sans=0;int xhx[maxn],top=-1;void init()//转换地图，把符号变成数字{ sans=0; top=-1; N=strlen(str); for(int i=0;i
              
               =0&&x==ma[i-1]&&x==ma[i-2]) return false; if(i+2
               
                =0&&x==ma[i+1]&&x==ma[i-1]) return false; return true;}void DFS(int x,int fl,LL ans){ if(x==top+1) { if(fl)sans+=ans; return; } for(int i=0;i<=2;i++) { int ti=xhx[x]; int tfl=fl,xx=i; if(i==0)tfl=1,xx=1; if(OK(ti,xx)) { ma[ti]=i; if(i==0) ma[ti]=1; DFS(x+1,tfl,ans*a[i]); ma[ti]=-1; } }}int main(){ while(~scanf("%s",&str)) { init(); int flag=1,fl=0; for(int i=2;i

转载于:https://www.cnblogs.com/107acm/p/9428323.html

你可能感兴趣的文章

lua源码在windows下的编译，以及添加新的c\c++模块