题目链接： 背单词
思路
我们设置一个三维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
40
| #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;
}
}
|