陈默

用户名：uq_40549581194

访问量：962

签　名：

等　　级
排　　名	4923
经　　验	1624
参赛次数	0
文章发表	4
年　　龄	18
在职情况	学生
学　　校	长江大学
专　　业	电子信息工程

　　自我简介：

TA的其他文章

烦人的校门口的大树
浏览：196

每天都想改学python系列之一行流改大小写
浏览：92

链表合并之我用了stl容器偷懒解法
浏览：174

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

李白打酒加强版动态规划

　　作者: 陈默　　　　发表时间：2022-08-31 21:24:11 浏览：504　|　评论：5　

原题链接：蓝桥杯2022年第十三届省赛真题-李白打酒加强版

分析：这是一道动态规划题，设f[i][j][k]表示走到了第i个位置，遇到了j个花，还剩k斗酒的合法方案数.

初始化很简单就是f[0][0][2]=1,因为一开始酒的数量是2

假如共遇到店n次，遇到花m次：

那么答案就是f[n+m-1][m-1][1],这是很容易理解的，因为我们共需要遇到m次花且最后一次一定是花，则走到倒数第二个位置时一定已经遇到了m-1个花，且由于遇到花后酒的数量会减少1，所以走到倒数第二个位置时酒的数量也必须是1.

下面开始进行状态转移方程的推导：

首先我们有必要对酒的奇偶性进行讨论，因为当走到第i个位置时酒的数量为偶，则第i个位置不可能为店，因为无论是奇数还是偶数，乘以2得到的数都是一个偶数，所以只有当k是偶数时第i个位置才可能是店，假如第i个位置是店，那么这个时候在第i-1个位置的酒的数量就是k/2，而遇到花的数量跟第i-1个位置是一样的都是j，这个很好理解，下面再看一下第i个位置是花的情况，那么第i-1个位置的酒的数量一定是k+1，因为在第i个位置消耗了1，而到达第i个位置遇到的花的数量就要比第i-1个位置遇到花的数量多1，因为我们现在是在假设第i个位置是花。

这就是这道题目的全部分析过程了，下面给出代码：
```cpp
#include<iostream>
using namespace std;
const int N=113;
const int mod=1e9+7;
long long f[N*2][N][N];//f[i][j][k]表示走到了第i个位置，遇到了j个花，还剩k斗酒的合法方案数 
int main()
{
	f[0][0][2]=1;//初始化
	int n,m;
	cin>>n>>m;
	for(int i=1;i<n+m;i++)
	for(int j=0;j<m;j++)
	for(int k=0;k<=m;k++)//酒的数量不能超过花的数量，否则就算之后一直是花也喝不完 
	{
		if(!(k&1))//k是偶数，则第i个位置可以是店，否则不可以是店
			f[i][j][k]=(f[i][j][k]+f[i-1][j][k>>1])%mod;
		if(j>=1)//无论k是奇数还是偶数，第i个位置都可以是花 
			f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;
	}
	printf("%lld",f[n+m-1][m-1][1]);
	return 0; 
}
```
参考链接：https://blog.csdn.net/AC__dream/article/details/124072351

0.0分

9 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

　　评论区

Bingbong

思路确实牛批

2023-04-06 15:48:23

KenHe

膜拜大佬

2022-10-15 20:39:15

早起床

牛啊

2022-10-09 18:18:11

吴起阳

我可算会了

2022-09-27 17:37:46

坚

2022-09-01 15:37:37

陈默

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

Biggest Number （C++代码）回溯法

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

李白打酒加强版动态规划

评论区

精彩推荐

矩阵乘法（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

求圆的面积（C语言代码）

不会做的

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

DNA （C语言描述，蓝桥杯）

C二级辅导-阶乘数列（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

母牛的故事（C语言代码）

陈默

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

Biggest Number （C++代码）回溯法

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

李白打酒加强版动态规划

评论区

精彩推荐

矩阵乘法 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

求圆的面积 （C语言代码）

不会做的

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

DNA （C语言描述，蓝桥杯）

C二级辅导-阶乘数列 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

母牛的故事 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

矩阵乘法（C++代码）

求圆的面积（C语言代码）

C二级辅导-阶乘数列（C语言代码）

C二级辅导-等差数列（C语言代码）

母牛的故事（C语言代码）