第十五届蓝桥杯第三期模拟赛第十题 ← 上楼梯
【问题描述】
小蓝要上一个楼梯,楼梯共有 n 级台阶(即小蓝总共要走 n 级)。小蓝每一步可以走 a 级、b 级或 c 级台阶。
请问小蓝总共有多少种方案能正好走到楼梯顶端?
【输入格式】
输入的第一行包含一个整数 n 。
第二行包含三个整数 a, b, c 。
【输出格式】
输出一行包含一个整数,表示答案。答案可能很大,请输出答案除以 1000000007 后的余数。
【样例输入】
4
1 2 3
【样例输出】
7
【评测用例规模与约定】
对于 30% 评测用例,1 <= a < b < c <= n <= 50。
对于 60% 评测用例,1 <= a < b < c <= n <= 1000。
对于所有评测用例,1 <= a < b < c <= n <= 1000000。
【算法分析】
● 本例用到的 vector 语法简介
vector<int> v(10); // 定义了10个 int 类型元素的向量 v,未初始化;
vector<int> v(10,1); //定义了10个 int 类型元素的向量 v,每个元素初始化为1。
● 1000000007,是最小的十位数质数。模1000000007,可以保证值永远在 int 的范围内。
● 此题解法,可由题目 https://blog.csdn.net/hnjzsyjyj/article/details/114990369 使用的“最后一步法”获得启发。由于本题是它的加难版本,本质上一致,所以本题亦可利用动态规划问题的“最后一步法”尝试求解。
据上,设状态 f(x) 表示走到第 x 阶台阶时共有多少种走法。进而,可确立状态转移方程为 f(n)=f(n-a)+f(n-b)+f(n-c)。但是,a、b、c 是在程序运行后输入的,是不定的。所以,无法预先根据 a、b、c 的值,依据“最后一步法”在代码中确定相应的边界条件。故在代码上,就需要有所变化,即不以a、b、c 的值作为确立边界的条件,而是以 a、b、c 的值作为分段计算的条件,进行累加计算。如下图所示。
也就是说,最终合并计算的值就是状态转移方程 f(n)=f(n-a)+f(n-b)+f(n-c) 要确立的值。
【算法代码】
#include <bits/stdc++.h>
using namespace std;int main() {int n,a,b,c;cin>>n>>a>>b>>c;vector<int> v(n+1,0);v[0]=1;for(int i=a; i<=n; i++) {v[i]=(v[i]+v[i-a])%1000000007;if(i>=b) v[i]=(v[i]+v[i-b])%1000000007;if(i>=c) v[i]=(v[i]+v[i-c])%1000000007;}cout<<v[n]<<endl;return 0;
}/*
in:
4
1 2 3out:
7
*/
若依据本题解法思路,则题目 https://blog.csdn.net/hnjzsyjyj/article/details/114990369 的代码如下所示:
#include <bits/stdc++.h>
using namespace std;int a=1,b=2,c=3;int main() { int n;cin>>n;vector<int> v(n+1,0);v[0]=1;for(int i=a; i<=n; i++) {v[i]=(v[i]+v[i-a])%1000000007;if(i>=b) v[i]=(v[i]+v[i-b])%1000000007;if(i>=c) v[i]=(v[i]+v[i-c])%1000000007;}cout<<v[n]<<endl;return 0;
}/*
in:5
out:13
*/
【参考文献】
https://www.ewbang.com/community/article/details/997972208.html
https://blog.csdn.net/weixin_45697711/article/details/121579057
https://blog.csdn.net/weixin_73332175/article/details/136502012
相关文章:

第十五届蓝桥杯第三期模拟赛第十题 ← 上楼梯
【问题描述】 小蓝要上一个楼梯,楼梯共有 n 级台阶(即小蓝总共要走 n 级)。小蓝每一步可以走 a 级、b 级或 c 级台阶。 请问小蓝总共有多少种方案能正好走到楼梯顶端?【输入格式】 输入的第一行包含一个整数 n 。 第二行包含三个整…...
第四题:星期一
题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 整个 20 世纪(1901 年 1 月 1 日至 2000 年 12 月 31 日之间),一共有多少个星期一?(不要告诉我你不知道今天是星期几…...

Mamba: Linear-Time Sequence Modeling with Selective State Spaces(论文笔记)
What can I say? 2024年我还能说什么? Mamba out! 曼巴出来了! 原文链接: [2312.00752] Mamba: Linear-Time Sequence Modeling with Selective State Spaces (arxiv.org) 原文笔记: What: Mamba: Linear-Time …...
2024蓝桥杯每日一题(区间DP)
备战2024年蓝桥杯 -- 每日一题 Python大学A组 试题一:游戏 试题二:石子合并 试题三:密码脱落 试题四:能量项链 试题一:游戏 【题目描述】 玩家一和玩家二共同玩一个小游戏。给定一个包含 N 个…...
LeetCode-2952. 需要添加的硬币的最小数量【贪心 数组 排序】
LeetCode-2952. 需要添加的硬币的最小数量【贪心 数组 排序】 题目描述:解题思路一:看提示主要是用贪心和排序。那我们肯定是首先对coins排序。然后依次遍历coins[i],获取当前可以获取金额范围,和判断是否加入新硬币。判断规则如下…...

新书速递——《可解释AI实战(PyTorch版)》
本书旨在帮助你实施最新的可解释AI技术,以构建公平且可解释的AI系统。可解释AI是当今AI研究中的热门话题,但只有少数资源和指南涵盖了所有重要技术,这些技术对实践者来说非常有价值。本书旨在填补这一空白。 本书读者对象 本书既适合那些有兴…...

国产数据库中统计信息自动更新机制
数据库中统计信息描述的数据库中表和索引的大小数以及数据分布状况,统计信息的准确性对优化器选择执行计划时具有重要的参考意义。本文简要整理了下传统数据库和国产数据库中统计信息的自动更新机制,以加深了解。 1、数据库统计信息介绍 优化器是数据库…...

【C++】入门C++(中)
好的,我们继续,这是 C专栏的第二篇博客,还没读过上一篇博客可以进入我创建的专栏阅读 入门C(上)再回来哦~ 下面我们要讲的第一个概念就是函数重载 函数重载 1. 函数重载概念 什么是函数重载? 简单来说…...

javaIO
file类 一个File类的对象可以表示一个具体的文件或目录 mkdir 创建单级文件夹 mkdirs 创建多级文件夹 delete 删除一个文件夹时,文件夹里面必须是空的 listfiles 将文件夹的子集放到一个file类型的数组中 输入及输出的概念 输入input 输出output 把jav…...

睿尔曼超轻量仿人机械臂之复合机器人底盘介绍及接口调用
机器人移动平台是一个包含完整成熟的感知、认知和定位导航能力的轮式机器人底盘产品级平台,产品致力于为各行业细分市场的商用轮式服务机器人提供一站式移动机器人解决方案,让合作伙伴专注在核心业务/人机交互的实现。以下是我司产品双臂机器人以及复合升…...

用JSch实现远程传输文件并打包成jar
本文将简单介绍一下 JSch 这个Java的第三方库的一个简单用法,并以此为实例,讲解 IntelliJ 中打包成 jar 包的2种方式。 实现目标 我们的目标是,做出一个jar包,它能够实现类似于 scp 命令的远程传输文件的功能。用法如下…...

2023年第十四届蓝桥杯大赛软件类省赛C/C++研究生组真题(代码完整题解)
C题-翻转⭐ 标签:贪心 简述:如果 S 中存在子串 101 或者 010,就可以将其分别变为 111 和 000,操作可以无限重复。最少翻转多少次可以把 S 变成和 T 一样。 链接: 翻转 思路:要求步骤最少->S每个位置最多修改一次->从头开始遍历不匹配就翻转->翻转不了就-1 …...

力扣刷题Days28-第二题-11.盛水最多的容器(js)
目录 1,题目 2,代码 3,学习与总结 3.1思路回顾 1,如何遍历 2,算法流程 3.2剖析问题 1,题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, h…...

文生图大模型三部曲:DDPM、LDM、SD 详细讲解!
1、引言 跨模态大模型是指能够在不同感官模态(如视觉、语言、音频等)之间进行信息转换的大规模语言模型。当前图文跨模态大模型主要有: 文生图大模型:如 Stable Diffusion系列、DALL-E系列、Imagen等 图文匹配大模型:如CLIP、Chinese CLIP、…...

算法学习——LeetCode力扣动态规划篇10(583. 两个字符串的删除操作、72. 编辑距离、647. 回文子串、516. 最长回文子序列)
算法学习——LeetCode力扣动态规划篇10 583. 两个字符串的删除操作 583. 两个字符串的删除操作 - 力扣(LeetCode) 描述 给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字符串中的一个…...

TASKPROMPTER
baseline模型的预训练权重就有1.6G! 多吓人呐,当时我就暂停下载了,不建议复现...

C之易错注意点转义字符,sizeof,scanf,printf
目录 前言 一:转义字符 1.转义字符顾名思义就是转换原来意思的字符 2.常见的转义字符 1.特殊\b 2. 特殊\ddd和\xdd 3.转义字符常错点----计算字符串长度 注意 : 如果出现\890,\921这些的不是属于\ddd类型的,,不是一个字符…...
等级保护测评无补偿因素的高风险安全问题判例(共23项需整改)
层面 控制点 要求项 安全问题 适用范围 充分条件 整改建议简要 安全物理环境 基础设施位置 应保证云计算基础设施位于中国境内 1.云计算基础设施物理位置不当 二级及以上 相关基础设施不在中国境内 云平台相关基础设施在中国境内部署 安全通信网络 网络架构 应…...
JavaScript笔记 09
目录 01 DOM操作事件的体验 02 获取元素对象的五种方式 03 事件中this指向问题 04循环绑定事件 05 DOM节点对象的常用操作 06 点亮盒子的案例 07 节点访问关系 08 设置和获取节点内容的属性 09 以上内容的小总结 01 DOM操作事件的体验 js本身是受事件驱动的脚本语言 什…...

操作教程|在MeterSphere中通过SSH登录服务器的两种方法
MeterSphere开源持续测试平台拥有非常强大的插件集成机制,用户可以通过插件实现平台能力的拓展,借助插件或脚本实现多种功能。在测试过程中,测试人员有时需要通过SSH协议登录至服务器,以获取某些配置文件和日志文件,或…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...

Springboot 高校报修与互助平台小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,高校报修与互助平台小程序被用户普遍使用,为…...