【NC16619】传球游戏

embedded/2024/12/22 16:20:04/

题目

传球游戏

动态规划

思路

这道题主要考察对状态转移的理解。说实话,动态规划问题只要想到了就简单,想不到就很难,除了像背包问题那一类有固定套路的题以外,其实大部分的动态规划问题都没什么所谓的公式。还是得多练,多见识不同的题型才能更好地思考动态规划问题。

题目中给定了 n n n 个人组成一个环,要求从第 x x x 个人开始,经过 m m m 次传球之后球又回到第 x x x 个人手中的不同方法数。其中 x x x 表示球最开始在的那个人,题目中是小蛮,这可以认为是一个定值。

首先需要明确的是,假设我现在身处这个环中,要接到球有几种可能?只有两种可能,要么从右边的人手中接到球,要么从左边的人手中接到球
其实如果最开始就是往这个方向想的话,那么离正确答案也就不远了。但是我也是这么想的,却没有得到正确答案,原因是什么呢?就是那种“感觉”没有培养到位,换句话说:题练少了。
明确了这一点之后,那么显然 ,球到我手里的不同方法数,其实就是球到我左边的人手里的方法数 + + + 球到我左边的人手里的方法数。
这样一来就有递推的感觉了,也就有动态规划的影子了。

那么按照动态规划的模板思考:

设置一个 d p [ i ] [ j ] dp[i][j] dp[i][j] 数组表示经过 i i i 次传球球又回到编号为 j j j 的人手中的不同方法数。则状态转移方程为:
d p [ i ] [ j ] = d p [ i − 1 ] [ ( j − 1 + n ) % n ] + d p [ i − 1 ] [ ( j + 1 ) % n ] dp[i][j]=dp[i-1][(j-1+n)\%n]+dp[i-1][(j+1)\%n] dp[i][j]=dp[i1][(j1+n)%n]+dp[i1][(j+1)%n]
注意是环形的,要取模。式子中的 % \% % 表示取模。
假设小蛮的编号为 0 0 0,那么最终的答案就是 d p [ m ] [ 0 ] dp[m][0] dp[m][0],即传了 m m m 次球球又回到编号为 0 0 0 的人手中。边界条件为 d p [ 0 ] [ 1... n − 1 ] = 0 , d p [ 0 ] [ 0 ] = 1 dp[0][1...n-1]=0,dp[0][0]=1 dp[0][1...n1]=0dp[0][0]=1,因为初始球就在编号为 0 0 0 的人手中,经过 0 0 0 次传球,不同的方法数为 1 1 1(球没动)

有了上面的思路就可以写出代码并解决问题了。但是不应满足于此,动态规划问题往往可以用滚动数组优化,这道题也行,具体见代码。

代码

#include <stdio.h>int main(void) {int n = 0, m = 0;scanf("%d%d", &n, &m);// 滚动数组,只保留两行,然后用奇偶性进行切换int dp[2][n], i = 0, j = 0, idx = 0;// 初始化for (i = 0; i < n; i++) {dp[0][i] = 0;}// 小蛮为0号dp[0][0] = 1;for (i = 1; i <= m; i++) {for (j = 0; j < n; j++) {idx = i & 1;  // idx仅仅是为了简化代码写法,可以去掉dp[idx][j] = dp[!idx][(j - 1 + n) % n] + dp[!idx][(j + 1) % n];}}printf("%d\n", dp[m & 1][0]);return 0;
}

http://www.ppmy.cn/embedded/19930.html

相关文章

OneFlow 概念清单

OneFlow 是一个深度学习框架&#xff0c;旨在提供高性能、易用性和灵活性。以下是 OneFlow 的一些主要特点和概念&#xff1a; 高性能&#xff1a; OneFlow 旨在利用现代硬件加速深度学习训练和推理&#xff0c;提供高性能的计算能力。它支持在单个 GPU 或多个 GPU 之间进行分布…

AI大模型探索之路-训练篇1:大语言模型微调基础认知

文章目录 前言一、微调技术概述二、微调的必要性三、大模型的微调方法四、微调过程中的技术细节五、微调后的模型评估与应用总结 前言 在人工智能的广阔研究领域内&#xff0c;大型预训练语言模型&#xff08;Large Language Models, LLMs&#xff09;已经成为推动技术革新的关…

架构师系列- 消息中间件(15)-kafka业务实战

7.1 顺序性场景 7.1.1 场景概述 假设我们要传输一批订单到另一个系统&#xff0c;那么订单对应状态的演变是有顺序性要求的。 已下单 → 已支付 → 已确认 不允许错乱&#xff01; 7.1.2 顺序级别 1&#xff09;全局有序&#xff1a; 串行化。每条经过kafka的消息必须严格…

构建安全高效的前端权限控制系统

✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天开心哦&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; ✨✨ 帅哥美女们&#xff0c;我们共同加油&#xff01;一起进步&am…

Redis技术总结

1.基本数据结构,底层原理,以及应用 String 底层使用了SDS简单动态字符,string一共三种编码方式,int,embstr,raw int主要存储long型整数 string有两个数据结构redisObject和SDS embstr和raw底层sds,主要区别是embstr的redisobject和sds连续存储在一起,而redisobject和s…

SpringBoot模块化时遇到Could not autowire. No beans of ‘xxxService‘ type found.错误

SpringBoot模块化时遇到Could not autowire. No beans of xxxService type found.错误 一、SpringBoot模块化时遇到Could not autowire. No beans of xxxService type found.错误二、解决办法一三、解决办法二 一、SpringBoot模块化时遇到Could not autowire. No beans of ‘xx…

UE4_动画基础_FootIK

角色由于胶囊体的阻挡&#xff0c;双脚与地面平行&#xff0c;不会与斜坡、台阶等贴合&#xff0c;有一条腿会处于悬空状态&#xff0c;通过双骨骼IK节点使一只脚太高&#xff0c;让后胶囊体下降&#xff0c;修正双脚的角度。这就是逆向运动IK的方法。 一、新建第三人称模板游戏…

react,Chart

一、基础图&#xff1a;https://ant-design-charts.antgroup.com/ Ant Design Charts 1. 首先要下载ant-design/charts&#xff0c;然后在页面中添加如下柱状图代码: import React from react; import { Column } from ant-design/chartsconst DemoColumn: React.FC () …