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≤10。
对于
100
%
100 \%
100% 的评测用例:
1
≤
N
,
M
≤
100
1 \leq N, M \leq 100
1≤N,M≤100。
蓝桥杯 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 <= 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]之间。
相关阅读
发表评论