Test

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

题目描述

微信图片_20220409224737.png 微信图片_20220409224743.png

算法

(动态规划) $O(n * m * k *c)$

一看到这道题我马上就想到了类似走迷宫dp问题, 都是有方向性(即把酒喝完)和 步骤性(到酒店还是到花)的问题, 只是多了一些限制条件(例如最后一次是花 等等)

于是我们可以大胆假设:

dp算法:闫氏dp分析法 (yxc yyds)

微信图片_20220409231759.png

解释:如果最后一步是到店,那么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总题解

微信图片_20220411231503.png

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;
}
使用 Hugo 构建
主题 StackJimmy 设计