蓝桥试题:传球游戏(二维dp)
一、题目描述
上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。
游戏规则是这样的:n 个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再次吹哨子时,传球停止,此时,拿着球没传出去的那个同学就是败者,要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题:有多少种不同的传球方法可以使得从小蛮手里开始传的球,传了 m 次以后,又回到小蛮手里。两种传球的方法被视作不同的方法,当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同的。比如有 3 个同学 1 号、2 号、3 号,并假设小蛮为 1 号,球传了 3 次回到小蛮手里的方式有 1->2->3->1 和 1->3->2->1,共 2 种。
输入描述
输入一行,有两个用空格隔开的整数 n,m (3≤n≤30,1≤m≤30) 。
输出描述
输出一行,有一个整数,表示符合题意的方法数。
输入输出样例
示例 1
输入
3 3
输出
2
二、代码演示
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] dp = new int[m + 1][n];dp[0][0] = 1;for (int i = 1; i <= m ; i++) { //第i次传球到j号同学的方案数for (int j = 0; j < n; j++) {dp[i][j] += dp[i - 1][(j + 1 + n) % n] + dp[i - 1][(j - 1 + n) % n];}}System.out.println(dp[m][0]);}
}
这段代码使用动态规划来解决传球问题,计算经过m次传球后球回到初始同学(0号)的方案数。以下是代码的详细解释:
动态规划数组初始化:
dp[i][j]表示经过i次传球后,球到达j号同学的方案数。初始状态
dp[0][0] = 1表示0次传球时球在0号同学手中。状态转移:
对于每次传球i(从1到m),遍历每个同学j(从0到n-1)。
当前状态
dp[i][j]由上一次传球到j的左右相邻同学的方案数之和得到。左右相邻同学通过取模运算处理环状结构,确保索引在有效范围内。
逻辑
每次传球只能传给 相邻同学(环形结构)。
因此,球到达
j号的方案数等于:
前一次球在
j号左侧同学手中的方案数((j - 1 + n) % n)加上 前一次球在
j号右侧同学手中的方案数((j + 1 + n) % n)。环形结构的处理
(j + 1 + n) % n:获取j号右侧同学的索引(自动处理j=n-1时的循环)。
(j - 1 + n) % n:获取j号左侧同学的索引(避免j=0时出现负数)。
相关文章:
蓝桥试题:传球游戏(二维dp)
一、题目描述 上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。 游戏规则是这样的:n 个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球࿰…...
迷你世界脚本小地图接口:Mapmark
小地图接口:Mapmark 彼得兔 更新时间: 2023-10-25 10:33:48 具体函数名及描述如下: 序号 函数名 函数描述 1 newShape(...) 新增一个形状(线,矩形,圆形) 2 deleteShape(...) 删除一个形状 3 setShapeColor(...) 设置…...
从零开始在Windows使用VMware虚拟机安装黑群晖7.2系统并实现远程访问
文章目录 前言1.软件准备2. 安装VMware17虚拟机3.安装黑群晖4. 安装群晖搜索助手5. 配置黑群晖系统6. 安装内网穿透6.1 下载cpolar套件6.2 配置群辉虚拟机6.3 配置公网地址6.4 配置固定公网地址 总结 前言 本文主要介绍如何从零开始在Windows系统电脑使用VMware17虚拟机安装黑…...
Qt6.8.2创建WebAssmebly项目使用FFmpeg资源
Qt6新出了WebAssmebly功能,可以将C写的软件到浏览器中运行,最近一段时间正在研究这方便内容,普通的控件响应都能实现,今天主要为大家分享如何将FFmpeg中的功能应用到浏览器中。 开发环境:window11,Qt6.8.2…...
Java阻塞队列深度解析:高并发场景下的安全卫士
一、阻塞队列的核心价值 在电商秒杀系统中,瞬时涌入的10万请求如果直接冲击数据库,必然导致系统崩溃。阻塞队列如同一个智能缓冲带,通过流量削峰和异步解耦两大核心能力,成为高并发系统的核心组件。 二、Java阻塞队列实现类对比 …...
软件信息安全性测试流程有哪些?专业软件测评服务机构分享
在数字化时代,软件信息安全性测试的重要性愈发凸显。尤其是对于企业来说,确保软件的安全性不仅是维护用户信任的关键,也是满足合规要求的必要条件。 软件信息安全性测试是指通过一系列系统化的测试手段,评估软件应用在受到攻击时…...
Linux - 网络基础(应用层,传输层)
一、应用层 1)发送接收流程 1. 发送文件 write 函数发送数据到 TCP 套接字时,内容不一定会立即通过网络发送出去。这是因为网络通信涉及多个层次的缓冲和处理,TCP 是一个面向连接的协议,它需要进行一定的排队、确认和重传等处理…...
C++11新特性:auto遇上const时的推导规则
当auto推导变量类型时,const修饰符会影响推导结果,我们具体看一下有哪些影响 1、普通变量 例如: const int ci 42; auto a ci; // a 的类型是 int (顶层 const 被忽略) const auto ca ci; // ca 的类型是 const int (顶层 const 被…...
hom_mat2d_to_affine_par 的c#实现
hom_mat2d_to_affine_par 的c#实现 背景:为课室贡献一个通用函数,实现halcon算子的同等效果,查询csdn未果,deepseek二哥与chtgpt大哥给不了最终程序,在大哥与二哥帮助下,最终实现同等效果。 踩坑…...
相机几何与标定:从三维世界到二维图像的映射
本系列课程将带领读者开启一场独特的三维视觉工程之旅。我们不再止步于教科书式的公式推导,而是聚焦于如何将抽象的数学原理转化为可落地的工程实践。通过解剖相机的光学特性、构建成像数学模型、解析坐标系转换链条,直至亲手实现参数标定代码࿰…...
GPTQ - 生成式预训练 Transformer 的精确训练后压缩
GPTQ - 生成式预训练 Transformer 的精确训练后压缩 flyfish 曾经是 https://github.com/AutoGPTQ/AutoGPTQ 现在是https://github.com/ModelCloud/GPTQModel 对应论文是 《Accurate Post-Training Quantization for Generative Pre-trained Transformers》 生成式预训练Tr…...
【Python项目】基于深度学习的电影评论情感分析系统
【Python项目】基于深度学习的电影评论情感分析系统 技术简介:采用Python技术、Flask框架、MySQL数据库、Word2Vec模型等实现。 系统简介:该系统基于深度学习技术,特别是Word2Vec模型,用于分析电影评论的情感倾向。系统分为前台…...
Redis特性总结
一、速度快 正常情况下,Redis 执⾏命令的速度⾮常快,官⽅给出的数字是读写性能可以达到 10 万 / 秒,当然这也取决于机器的性能,但这⾥先不讨论机器性能上的差异,只分析⼀下是什么造就了 Redis 如此之快,可以…...
深入理解PHP的内存管理与优化技巧
深入理解PHP的内存管理与优化技巧 PHP作为一种广泛使用的服务器端脚本语言,其内存管理机制对于应用程序的性能和稳定性至关重要。本文将深入探讨PHP的内存管理机制,并提供一些优化技巧,帮助开发者更好地理解和优化PHP应用程序的内存使用。 …...
java常见的几种并发安全问题及解决方案
项目场景: 并发的应用场景,在开发过程会经常遇到。 例如:服务应用启动后,需要简单统计接口的总访问量;实时更新订单状态,成交总额。 问题描述: 比如统计接口访问次数,如下的实现&a…...
介绍一下安装时情况 kubernetes 集群
1.安装命令执行完毕 最开始告诉我们应用的版本 v1.29.14前置检测下载镜像写入证书因为当前我们所有的 kubernetes 集群的组件之间的联通 都是基于HTTPS协议实现的 补充知识点:BS架构,即Browser/Server(浏览器/服务器)架构模式&a…...
Dify部署踩坑指南(Windows+Mac)
组件说明 Dify踩坑及解决方案 ⚠️ 除了修改镜像版本,nginx端口不要直接修改docker-compose.yaml !!!!!!! 1、更换镜像版本 这个文件是由.env自动生成的,在.env配置 …...
安科瑞新能源充电桩解决方案:驱动绿色未来,赋能智慧能源
安科瑞顾强 引言 在“双碳”目标与新能源汽车产业高速发展的双重驱动下,充电基础设施正成为能源转型的核心环节。安科瑞电气股份有限公司凭借在电力监控与能效管理领域20余年的技术积淀,推出新一代新能源充电桩解决方案,以智能化、高兼容性…...
深入剖析Java代理模式:静态代理与动态代理的实战应用
代理模式是Java开发中最重要的设计模式之一,广泛应用于性能监控、访问控制、日志记录等场景。本文将带你全面掌握代理模式的实现原理,并通过3种不同的代码实现方式,彻底理解这一核心设计模式的应用技巧。 一、代理模式的核心价值 代理模式(Proxy Pattern)通过创建代理对…...
JVM与性能调优详解
以下是关于 JVM与性能调优 的详细解析,结合理论、实践及常见问题,分多个维度展开: 一、JVM性能调优的核心目标 性能调优的核心目标是通过优化内存管理、垃圾回收(GC)策略和线程管理,实现以下平衡ÿ…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
