牛客练习赛35 背单词

发表于 | 更新于 | 分类于 | 阅读次数：

题目链接： 背单词

思路

我们设置一个三维dp数组 ，$dp[i][j][k]$ 代表 第i个字符是j状态（j为0代表是元音，1为辅音）,同时该j状态已经持续了k个字母，这样我们就能唯一确定该字符序列由什么组成了。

$dp[1][0][1]$ = 5 , $dp[1][1][1]$ = 21. 这是初始化。

当i从2开始遍历的时候，我们先确定一下$dp[i][0][1]$ 以及 $dp[i][1][1]$的状态，之后的话，

$ dp[i][0][j] $ = $dp[i - 1][0][j - 1]$ * 5

$ dp[i][1][j] $ = $dp[i - 1][1][j - 1]$ * 21

就很好求了。 (记录一下在next主题中调用数学公式：需要在文章开头打开mathjax开关（mathjax: true), 同时注意配置中math中改为true)

如果求$dp[i][0][1]$的话，说明第i个字符是元音，且第i - 1个字符是辅音，至于前边有多少个辅音，我们就需要通过循环遍历去找了。

dp的题真的是妙啊，由前边的状态推后边的状态，一层一层的求出来答案。看来以后还要多多训练这方面的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
long long dp[5001][2][51];
long long mod = 1e9 + 7;
int main()
{
    int T,N,A,B;
    cin >> T;
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        cin >> N >> A >> B;
        long long sum = 0;
        dp[1][0][1] = 5;
        dp[1][1][1] = 21;
        for(int i = 2; i <= N; ++i)
        {
            for(int j = 1; j <= min(i - 1, B) ; ++j)
            dp[i][0][1] = (dp[i][0][1] + dp[i - 1][1][j] * 5) % mod;
            for(int j = 1; j <= min(i - 1, A); ++j)
            dp[i][1][1] = (dp[i][1][1] + dp[i - 1][0][j] * 21) % mod;
            for(int j = 2; j <= min(i , A); ++j)
            dp[i][0][j] = dp[i - 1][0][j - 1] * 5 % mod;
            for(int j = 2; j <= min(i, B); ++j)
            dp[i][1][j] = dp[i - 1][1][j - 1] * 21 % mod;
        }
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 0; j <= 1; ++j)
            {
                for(int k = 1; k <= 50; ++k)
                {
                    sum += dp[i][j][k];
                }
            }
        }
        cout << sum % mod << endl;
    }
}