动态规划计数型DP：dobra

令人愉快的单词(dobra)
时间限制： 0.1 秒
空间限制： 32 MB
【问题描述】
Lea 在她的一生中碰到过很多单词。其中的很大一部分都使她不愉快。作为
补偿，她开始创造一些愉快的单词。 Lea 通过写下一些看起来很不错的字母在一
张纸上来创造新单词。接下来，她擦掉一些看起来最令人讨厌的字母，并用'_'
来代替它们。接下来，她想要用更令人接受的字母替换掉这些下划线来构成一个
令人愉快的单词。
Lea 认为一个单词是愉快的当且仅当这个单词不包括 3 个连续的元音，不包
括 3 个连续的辅音并且包括至少一个'L'。
在克罗地亚文中，属于元音的字母只有 A, E, I, O, U。其它的都是辅音。
【输入文件】
输入文件 dobra.in 只有 1 行，为一个不超过 100 个字符的字符串。这个字符
串只包括大写的英文字母和'_'。数据保证输入中的'_'不超过 10 个。
【输出文件】
输出文件 dobra.out 包括一个整数，表示通过替换输入中的下划线可以构成
多少个令人愉快的单词。
注意：请使用 64 位整数类型。对于 C/C++语言，请使用 long long，对于 Pascal
语言，请使用 int64。
【输入输出样例】
input
L_V
input
V__K
input
JA_BU_K_A
output
5
output
10
output
485

三维数组DP，第一维指枚举到了那位，第二维中

　　下标0指连续有一个辅音并没有出现过三元或三辅的情况数

　　下标1指连续有两个辅音并没有出现过三元或三辅的情况数

　　下标2指连续有一个元音并没有出现过三元或三辅的情况数

　　下标4指连续有两个元音并没有出现过三元或三辅的情况数

第三维中指是否出现过‘L’。

看起来复杂其实思路很简单

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 char s[];

 long long dp[][][];

 bool ISyuan(char c)

 {return c=='A'||c=='E'||c=='I'||c=='O'||c=='U';}

 int main()

 {

     freopen("dobra.in","r",stdin);

     freopen("dobra.out","w",stdout);

     scanf("%s",s+);

     s[]='';

     int len=strlen(s)-,tot=;

     for(int i=;i<=len;i++)

     {

         if(s[i]=='_'){

             tot++;

         }

         else{

             if(s[i-]<='Z'&&s[i-]>='A')

                 if(s[i+]<='Z'&&s[i+]>='A')

                     if(ISyuan(s[i-])==ISyuan(s[i])&&ISyuan(s[i])==ISyuan(s[i+])){

                         printf("0\n");

                         return ;

                     }

         }

     }

     long long total=;

     for(;tot--;)total*=26ll;

     if(ISyuan(s[])){

         dp[][][]=1ll;

     }

     else{

         if(s[]=='L')

             dp[][][]=1ll;

         else if(s[]!='_')

             dp[][][]=1ll;

         else{

             dp[][][]=;

             dp[][][]=;

             dp[][][]=;

         }

     }

     for(int i=;i<=len;i++)

     {

         if(s[i]=='_'){

             dp[i][][]=dp[i-][][]*25ll;

             dp[i][][]=dp[i-][][]+dp[i-][][]*26ll;

             dp[i][][]+=dp[i-][][]*20ll;

             dp[i][][]+=dp[i-][][]*21ll+dp[i-][][];

             dp[i][][]+=dp[i-][][]*5ll;

             dp[i][][]+=dp[i-][][]*5ll;

             dp[i][][]=dp[i-][][]*20ll+dp[i-][][]*20ll;

             dp[i][][]=(dp[i-][][]+dp[i-][][])*21ll+dp[i-][][]+dp[i-][][];

             dp[i][][]=dp[i-][][]*20ll;

             dp[i][][]=dp[i-][][]*21ll+dp[i-][][];

             dp[i][][]=dp[i-][][]*5ll+dp[i-][][]*5ll;

             dp[i][][]=dp[i-][][]*5ll+dp[i-][][]*5ll;

             dp[i][][]=dp[i-][][]*5ll;

             dp[i][][]=dp[i-][][]*5ll;

         }

         else{

             if(ISyuan(s[i])){

                 dp[i][][]=dp[i][][]=dp[i][][]=dp[i][][]=0ll;

                 dp[i][][]=dp[i-][][]+dp[i-][][];

                 dp[i][][]=dp[i-][][]+dp[i-][][];

                 dp[i][][]=dp[i-][][];

                 dp[i][][]=dp[i-][][];

                 dp[i][][]=dp[i-][][]+dp[i-][][];

                 dp[i][][]=dp[i-][][]+dp[i-][][];

             }

             else{

                 dp[i][][]=dp[i][][]=dp[i][][]=dp[i][][]=0ll;

                 if(s[i]=='L'){

                     dp[i][][]=dp[i][][]=dp[i][][]=dp[i][][]=dp[i][][]=0ll;

                     dp[i][][]=dp[i-][][]+dp[i-][][]+dp[i-][][]+dp[i-][][];

                     dp[i][][]=dp[i-][][]+dp[i-][][];

                     dp[i][][]=dp[i-][][]+dp[i-][][];

                     dp[i][][]+=dp[i-][][]+dp[i-][][];

                 }

                 else{

                     dp[i][][]=dp[i-][][]+dp[i-][][];

                     dp[i][][]=dp[i-][][]+dp[i-][][];

                     dp[i][][]=dp[i-][][]+dp[i-][][];

                     dp[i][][]=dp[i-][][]+dp[i-][][];

                     dp[i][][]=dp[i-][][];

                     dp[i][][]=dp[i-][][];

                 }

             }

         }

     }

     long long off=dp[len][][]+dp[len][][]+dp[len][][]+dp[len][][]+dp[len][][]+dp[len][][];

     printf("%lld\n",total-off);

     return ;

 }

其实这道题用搜索，只有三类状态，可以AC，代码量只有50行，囧

巴特西

动态规划计数型DP：dobra

最新文章

热门文章

巴特西

动态规划 计数型DP：dobra

最新文章

热门文章

动态规划计数型DP：dobra