balabala
[//]: # (推荐题解模板,请替换blablabla等内容 ^^)
题目描述

算法
(动态规划) $O(n * m * k *c)$
一看到这道题我马上就想到了类似走迷宫dp问题,
都是有方向性(即把酒喝完)和 步骤性(到酒店还是到花)的问题,
只是多了一些限制条件(例如最后一次是花 等等)
于是我们可以大胆假设:
dp算法:闫氏dp分析法 (yxc yyds)

解释:如果最后一步是到店,那么j应该大于0,因为至少有最后一步到店,到花同理,
如果最后一步是到店,那么上一步手里有的酒应该是k / 2,也是因此我们的k应该整除于2
如果最后一步是到花,那么上一步手里有的酒应该是k + 1。
注意:这里的方案都是合法方案
时间复杂度
由于n, m 最大为100,则李白手里的酒不应该超过100斗,否则遇上的花喝不完酒
因此 时间复杂度大概为:100 * 100 * 100 * 2 (10的6次方,okk)
C++ 代码(四重循环)
注意:初始化的时候我把 f[0][0][2][1] 初始化为1,其他f[0][0][k][c]都为0,
表示一开始只有李白手里拿2斗酒这一种情况。
(如果初始化 f[0][0][2][0] = 1,其他 f[0][0][k][c] 为0也可)
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
41
|
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1000000007;
int n, m, f[N][N][N][2];
int main()
{
scanf("%d%d", &n, &m); // 按照题目的来, 原先写成m个店, n朵花实在太蠢, 看得自己都一愣一愣的
for(int i = 0; i <= m; i ++ )
{
for(int j = 0; j <= n; j ++ )
{
for(int k = 0; k <= m; k ++ ) // 手中的酒枚举到m即可, 因为不会超过花的个数
{
for(int c = 0; c < 2; c ++ )
{
if(i == 0 && j == 0 && k == 2 && c == 1)
f[i][j][k][c] = 1;
if(i == 0 && j == 0)
continue;
if(j > 0 && c == 1 && k % 2 == 0)
{
f[i][j][k][c] = (f[i][j - 1][k / 2][0] + f[i][j - 1][k / 2][1]) % M;
}
if(i > 0 && c == 0 && k >= 0)
{
f[i][j][k][c] = (f[i - 1][j][k + 1][0] + f[i - 1][j][k + 1][1]) % M;
}
}
}
}
}
printf("%d", f[m][n][0][0]);
return 0;
}
|
(分割线)
这里再附上听完y总的题解的解法,时间复杂度O(n * m * k)
视频链接
y总题解

C++ 代码(三重循环)
注意:初始化的时候把 f[0][0][2] 初始化为1,其他 f[0][0][k] 都为0,
表示一开始只有李白手里拿2斗酒这一种情况。
最后打印答案的时候不是打印 f[n][m][0] ,因为这么打印是无法区分最后是到花还是到店,
我们可以往前推一步,如果最后到花,那么喝完的上一步应该是f[m - 1][n][1],
所以最后答案是f[m - 1][n][1]
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
|
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1000000007;
int n, m, f[N][N][N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i <= m; i ++ )
{
for(int j = 0; j <= n; j ++ )
{
for(int k = 0; k <= m; k ++ ) // 手中的酒枚举到m即可, 因为不会超过花的个数
{
if(i == 0 && j == 0 && k == 2)
f[i][j][k] = 1;
if(i == 0 && j == 0)
continue;
if(i > 0)
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k + 1]) % M;
if(j > 0 && k % 2 == 0)
f[i][j][k] = (f[i][j][k] + f[i][j - 1][k / 2]) % M;
}
}
}
printf("%d", f[m - 1][n][1]);
return 0;
}
|