【DP】第十三届蓝桥杯省赛C++ B组《李白打酒加强版》(C++)
【题目描述】
话说大诗人李白,一生好饮。
幸好他从不开车。
一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。
他边走边唱:
无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。
这一路上,他一共遇到店 N 次,遇到花 M 次。
已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序,有多少种不同的可能?
注意:壶里没酒 (0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。
【输入格式】
第一行包含两个整数 N 和 M。
【输出格式】
输出一个整数表示答案。由于答案可能很大,输出模 1000000007 的结果。
【数据范围】
对于 40% 的评测用例:1≤N,M≤10。
对于 100% 的评测用例:1≤N,M≤100。
【输入样例】
5 10
【输出样例】
14
【样例解释】
如果我们用 0 代表遇到花,1 代表遇到店,14 种顺序如下:
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
【思路】
关键是酒的数量不可能多于遇到花的次数,否则不可能喝光酒。
状态表示:f[i][j][k],i 表示当前遇到店的数量、j 表示当前遇到花的数量,k 表示当前酒的数量。
状态属性:当前所有数量的集合。
状态表示:当前f[i][j][k]刚遇到店还是刚遇到花,f[i][j][k] = f[i-1][j][k/2] + f[i][j-1][k+1]
【代码】
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110, MOD = 1e9 + 7;int n, m;
int f[N][N][N];int main()
{cin >> n >> m;//初始状态:没遇到店和花,有2斗酒f[0][0][2] = 1;for (int i = 0; i <= n; i ++ )for (int j = 0; j <= m; j ++ )for (int k = 0; k <= m; k ++ ){//把当前值赋给变量是为了代码简洁,需要加上 & 才能保证取出原数组中元素的地址。int& v = f[i][j][k];//刚遇到的是店,需要判断 i >= 1 并且花是偶数if (i && k % 2 == 0) v = (v + f[i - 1][j][k / 2]) % MOD;//刚遇到的是花,需要判断 j >= 1if (j) v = (v + f[i][j - 1][k + 1]) % MOD;}//最后的状态即为遇到花后,酒刚好喝完。cout << f[n][m - 1][1] << endl;return 0;
}相关文章:
【DP】第十三届蓝桥杯省赛C++ B组《李白打酒加强版》(C++)
【题目描述】 话说大诗人李白,一生好饮。 幸好他从不开车。 一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。 他边走边唱: 无事街上走,提壶去打酒。 逢店加一倍,遇花喝一斗。 这一路上&am…...
数据结构试卷第九套
1.时间复杂度 2.树,森林,二叉树的转换 2.1树转二叉树 给所有的兄弟节点之间加一条连线;去线,只保留当前根节点与第一个叶子节点的连线,删除它与其他节点之间的连线;然后根据左孩子右兄弟进行调整…...
【Linux第三课-基础开发工具的使用】yum、vim、gcc/g++编译器、gdb、Make/Makefile编写、进度条程序、git命令行简单操作
目录 yum - 软件包管理器快速认识yum快速使用yumyum搜索yum安装yum卸载 yum的周边 - yum的整个生态问题 vim快速介绍vimvim的模式命令模式插入模式低行模式 常见模式 -- 命令、低行命令模式 -- 光标的移动命令模式 -- 复制粘贴、剪贴、删除命令模式 -- 小写/大写替换模式命令模…...
Redis:ClassCastException【bug】
Redis:ClassCastException【bug】 前言版权Redis:ClassCastException【bug】错误产生相关资源控制器:UserController("/user")配置:RedisConfiguration实体类:User数据表:User 解决 最后 前言 2…...
JSON 配置文件
JSON 配置文件的作用 JSON 是一种数据格式,在实际开发中, JSON 总是以配置文件的形式出现。小程序项目中也不例外:通过不同的 .json 配置文件,可以对小程序项目进行不同级别的配置。 小程序项目中有 4 种 json 配置文件࿰…...
由浅到深认识Java语言(6):控制流程语句
该文章Github地址:https://github.com/AntonyCheng/java-notes 在此介绍一下作者开源的SpringBoot项目初始化模板(Github仓库地址:https://github.com/AntonyCheng/spring-boot-init-template & CSDN文章地址:https://blog.c…...
lv17 安防监控项目实战 3
代码目录 框架 our_storage 编译最终生成的目标文件obj 编译生成中间的.o文件 data_global.c 公共资源定义(使用在外extern即可)定义了锁定义了条件变量消息队列id、共享内存id、信号量id及key值发送短信、接收短信的号码向消息队列发送消息的函数&am…...
文本处理基本方法
目录 分词 jieba 词性标注 😆😆😆感谢大家观看😆😆😆 分词 在中文文本中,由于词与词之间没有明显的界限符,如英文中的空格,因此分词是中文自然语言处理的一个基础且…...
Java面试题(Spring篇)
💟💟前言 友友们大家好,我是你们的小王同学😗😗 今天给大家打来的是 Java面试题(Spring篇) 希望能给大家带来有用的知识 觉得小王写的不错的话麻烦动动小手 点赞👍 收藏⭐ 评论📄 小王的主页…...
操作系统:malloc与堆区内存管理
malloc是函数而不是系统调用,他的底层是同调调用brk和mmap这两个系统调用实现功能的,具体选择brk还是mmap要看申请的空间大小以及malloc中的阈值(一般是128kb) 注意申请的空间只有使用才会触发缺页中断映射到物理内存 不理解的话先…...
javaSwing推箱子游戏
一、简介 策略性游戏可以锻炼人的思维能力还能缓解人的压力,使人们暂时忘却生活当中的烦恼,增强人们的逻辑思维能力,游戏的艺术美也吸引着越来越多的玩家和厂商,寓教于乐,在放松人们心情的同时还可以活跃双手。在人类…...
JAVA多线程之JMM
文章目录 1. Java内存模型2. 内存交互3. 三大特性3.1 可见性3.1.1 可见性问题3.1.2 原因3.1.3 解决方法 3.2 原子性3.3 有序性 4. 指令重排5. JMM 与 happens-before5.1 happens-before关系定义5.2 happens-before 关系 在继续学习JUC之前,我们现在这里介绍一下Java…...
Windows10 专业版 系统激活
Windows10 专业版 系统激活 参考: Windows10系统激活技巧 第一步:在电脑桌面,新建一个文本文档 第二步:打开文本文档,输入以下代码后,直接保存关闭文档 slmgr/skms kms.03k.org slmgr/ato 第三步࿱…...
C#使用LINQ和EF Core
在实际应用中,您可以使用 LINQ 查询 EF Core 来执行各种数据库操作。通过 LINQ,您可以轻松地过滤、排序、分组和连接数据。 要使用LINQ查询EF Core中的数据,您可以按照以下步骤进行操作: 首先,确保您已经安装了 Entit…...
数字人解决方案— SadTalker语音驱动图像生成视频原理与源码部署
简介 随着数字人物概念的兴起和生成技术的不断发展,将照片中的人物与音频输入进行同步变得越来越容易。然而,目前仍存在一些问题,比如头部运动不自然、面部表情扭曲以及图片和视频中人物面部的差异等。为了解决这些问题,来自西安…...
HTML5语法总结
文章目录 一.HTML基本框架二.标题标签三.段落标签四.换行与水平线标签五.文本格式化标签(加粗、倾斜、下划线、删除线)六.图像标签扩展:相对路径,绝对路径与在线网址 七.超链接标签八.音频标签九.视频标签十.列表标签十一.表格标签扩展:表格结构标签合并…...
在github下载的神经网络项目,如何运行?
github网页上可获取的信息 在github上面,有一个requirements.txt文件,该文件说明了项目要求的python解释器的模块。 - 此外,还有一个README.md文件,用来说明项目的运行环境以及其他的信息。例如python解释器的版本是3.7、PyTorc…...
spring boot学习第十四篇:使用AOP编程
一、基本介绍 1,什么是 AOP (1)AOP 为 Aspect Oriented Programming 的缩写,意为:面向切面编程,通过预编译方式和运行期动态代理实现程序功能的统一维护的一种技术。 (2)利用 AOP…...
凯特信安云签解决方案
联合解决方案 凯特信安基于《电子签名法》设计“云签服务方案”,应用人脸识别、电子签章签名云服务等技术,支持多个自然人、多个企业等签名,满足各种移动终端签署的应用场景。面向不动产登记、工改系统等社会公众服务系统,针对自然…...
【xr806开发板使用】连接wifi例程实现
##开发环境 win10 WSL ##1、环境配置 参考:https://aijishu.com/a/1060000000287513 首先下载安装wsl 和ubuntu https://docs.microsoft.com/zh-cn/windows/wsl/install (1)安装repo: 创建repo安装目录: mkdir ~/…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...
系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文通过代码驱动的方式,系统讲解PyTorch核心概念和实战技巧,涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...
AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)
Name:3ddown Serial:FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名:Axure 序列号:8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...
Python环境安装与虚拟环境配置详解
本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南,适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者,都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...
ubuntu中安装conda的后遗症
缘由: 在编译rk3588的sdk时,遇到编译buildroot失败,提示如下: 提示缺失expect,但是实测相关工具是在的,如下显示: 然后查找借助各个ai工具,重新安装相关的工具,依然无解。 解决&am…...
VSCode 没有添加Windows右键菜单
关键字:VSCode;Windows右键菜单;注册表。 文章目录 前言一、工程环境二、配置流程1.右键文件打开2.右键文件夹打开3.右键空白处打开文件夹 三、测试总结 前言 安装 VSCode 时没有注意,实际使用的时候发现 VSCode 在 Windows 菜单栏…...
