[动态规划][蓝桥杯 2022 省 B] 李白打酒加强版 -- 代码注释含详解

小明 2025-05-07 23:58:00 6

P8786 [蓝桥杯 2022 省 B] 李白打酒加强版(洛谷)

���谷题目链接

李白打酒很快活，而我打了一晚上代码才把这题弄懂🥲

  • P8786 [蓝桥杯 2022 省 B] 李白打酒加强版(洛谷)
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
      • 提示
      • \***\*\*\*\*\***\*\*\***\*\*\*\*\***\*\*\*\*\***\*\*\*\*\***\*\*\***\*\*\*\*\***
      • 👏图示解析:
      • ⌨️代码：
      • ❤️当然是令人happy的`过啦!`:
      • 🤣废话解析部分
        • 根据要求分析动态转移方程
        • 分析边界值索引

          题目描述

          话说大诗人李白，一生好饮。幸好他从不开车。

          一天，他提着酒壶，从家里出来，酒壶中有酒 2 2 2 斗。他边走边唱：

          无事街上走，提壶去打酒。

          逢店加一倍，遇花喝一斗。

          这一路上，他一共遇到店 N N N 次，遇到花 M M M 次。已知最后一次遇到的是花，他正好把酒喝光了。

          请你计算李白这一路遇到店和花的顺序，有多少种不同的可能?

          注意：壶里没酒（ 0 0 0 斗）时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

          输入格式

          第一行包含两个整数 N N N 和 M M M。

          输出格式

          输出一个整数表示答案。由于答案可能很大，输出模 1000000007 1000000007 1000000007（即 1 0 9 + 7 10^9+7 109+7）的结果。

          样例 #1

          样例输入 #1

          5 10

          样例输出 #1

          14

          提示

          【样例说明】

          如果我们用 0 代表遇到花，1 代表遇到店， 14 14 14 种顺序如下:

          010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100

          【评测用例规模与约定】

          对于 40 % 40 \% 40% 的评测用例： 1 ≤ N , M ≤ 10 1 \leq N, M \leq 10 1≤N,M≤

          对于 100 % 100 \% 100% 的评测用例： 1 ≤ N , M ≤ 100 1 \leq N, M \leq 100 1≤N,M≤

          蓝桥杯 2022 省赛 B 组 I 题。

          ********************************

          👏图示解析:

          动态转移方程：

          f[i + 1][j + 1][k - 1] += f[i][j][k];

          f[i + 1][j][k * 2] += f[i][j][k];

          相关图解：

          ⌨️代码：

          #include 
using namespace std;
const int mod = 1000000007;				//用来取模
//const int mod = 1e9+7;				//这样写也是一样的
int dfs[201][101][101];					//dfs[N+M][M][M]
//dfs[所在的位置][这个位置喝酒的次数][该位置的酒量]
//def[i][N][k]
//因为 N  n >> m;
	dfs[0][0][2] = 1;
	for (int i = 0; i
The End

标签：

微信