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

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

洛谷题目链接

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

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

题目描述

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

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

无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

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

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

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

输入格式

第一行包含两个整数 和 。

输出格式

输出一个整数表示答案。由于答案可能很大，输出模 （即 ）的结果。

样例 #1

样例输入 #1

5 10

样例输出 #1

14

提示

【样例说明】

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

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

【评测用例规模与约定】

对于 的评测用例：。

对于 的评测用例：。

蓝桥杯 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 <iostream>
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 <= 100 并且 M <= 100


int main()
{
	int n, m;
	cin >> n >> m;
	dfs[0][0][2] = 1;
	for (int i = 0; i < m + n; i ++)
	{//大循环表示走了m + n步，不多也不少。
		for (int j = 0; j < m; j ++)
		{//0~m代表喝酒m次，也就是喝酒的次数恰好为看花的次数，不多也不少。
			for (int k = 0; k <= m; k ++)
			{//k表示这个位置的酒量，可以是0，也可以和看花的次数一样
				if (dfs[i][j][k])
				{//如果这个位置存在可能到达的顺序，以下两种情况将都会发生

					//1.下一步是进入酒店的情况
					if (k <= 50) dfs[i+1][j][k*2] = (dfs[i][j][k] + dfs[i+1][j][k*2]) % mod;
					//测试用//printf("dfs[%d][%d][%d] = %d\n", i+1, j, k*2, dfs[i+1][j][k*2]);
					/*
						进入酒店，酒量翻倍，
						那么如果酒量为50，翻倍就会超过所能喝酒的最大次数上限,
						这时数据可能会不符合题目的给定条件和范围,
						又因为N，M最大可以是100，所以这个50恰好取到。
					 */


					//2.下一步是进入花店的情况 (也就是喝一口酒)
					if (k > 0) dfs[i+1][j+1][k-1] = (dfs[i][j][k] + dfs[i+1][j+1][k-1]) % mod;
					//测试用//printf("dfs[%d][%d][%d] = %d\n", i+1, j+1, k-1, dfs[i+1][j+1][k-1]);
					/*
						根据题意，酒量如果是0就不能再喝酒了，
						所以酒量必须要比零大才可以喝酒
					*/

				}
			}
		}
	}

	cout << dfs[n + m][m][0];
}

❤️当然是令人happy的过啦!:

🤣废话解析部分

根据要求分析动态转移方程

先来谈谈题目的要求，走 n 步，总共需要喝掉 m 次酒，每一步都只有两种可能的选择来进入到下一步:

1.进入酒店
2.喝一口酒

• 如果是进入酒店，那么 dfs[i][j][k]中的j不变（j 表示到现该位置喝了几口酒），k*2，（k 表示身上的酒量）。
• 如果是喝一口酒，那么 dfs[i][j][k]中的j+1（表示又喝了一口酒），k-1表示身上的酒量减少了。

再结合我们画出来的演示图，就不难得到动态转移方程了（为了方便阅读，又写了一遍）

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

分析边界值索引

for (int i = 0; i < m + n; i ++)
	{//大循环表示走了m + n步，不多也不少。
		for (int j = 0; j < m; j ++)
		{//0~m代表喝酒m次，也就是喝酒的次数恰好为看花的次数，不多也不少。
			for (int k = 0; k <= m; k ++)
			{//k表示这个位置的酒量，可以是0，也可以和看花的次数一样
				if (dfs[i][j][k])
				{//如果这个位置存在可能到达的顺序，以下两种情况将都会发生

代码中出现了三处的边界值，其中i循环和j循环不需要管理最后的边界位置，只需要知道，i循环进行了m + n次，表示走了m + n步，经过了m + n个位置。

同样的，j循环每一步喝酒的次数可能性，这里的思想类似于桶排序，主要是利用哈希属性来进行映射。

j表示看花次数，也是喝酒的次数，范围在[0, m - 1]，其实也可以是[1, m]，如果是[1, m]，最后答案的索引要进行更改。

k表示李白身上的酒量，范围在[0, M]之间。