衢州市网站建设_网站建设公司_MySQL_seo优化

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：历年CSP-X复赛真题解析 | 汇总

【题目来源】

洛谷：[B4089 CSP-X2020 山东] 勇敢的津津 - 洛谷

【题目描述】

津津是个勇敢的孩子，总是做一些挑战自己的事情。一天津津来到一条宽为L LL米的小河边，河道的一边到另一边需要途径N NN块较大的石墩，每块石墩到这一边岸边之间距离d i d_idi​米（石墩不占距离，只考虑石墩的中间点到这一边岸边之间距离）。津津想踩着这些石墩从小河的这一边跳到另一边（不落入水中），一次可以跳过几块石墩。已知津津每次最多跳M MM米的距离，那么津津最少跳几次就能从这一边跳到另一边？

【输入】

第一行包含三个整数L , N , M L,N,ML,N,M，分别小河的宽度、石墩数和津津跳的最远距离。

接下来N NN行，每行一个整数，第i ii行的整数d i ( 0 < d i < L ) d_i(0\lt d_i \lt L)di​(0<di​<L)，表示第i ii块石墩与这一边岸边的距离，保证石墩之间的距离和最靠边的石墩到这一边岸边的距离小于等于M MM。这些石墩按与起点距离从小到大的顺序给出，且不会有两个石墩出现在同一个位置。

【输出】

一个整数，即最少的跳跃次数。

【输入样例】

10 4 2 2 4 6 8

【输出样例】

5

【算法标签】

《洛谷 B4089 勇敢的津津》 #动态规划DP# #贪心# #CSP-X小学组# #2020# #山东#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=505;// 定义常量N，最大数组大小intL,m,n;// L: 跳跃长度上限, m: 最小跳跃距离, n: 石头数量inta[N],dp[N];// a: 存储石头位置, dp: 动态规划数组intmain(){cin>>L>>n>>m;// 输入跳跃长度上限、石头数量和最小跳跃距离for(inti=1;i<=n;i++)// 输入n个石头的位置cin>>a[i];a[n+1]=L;// 在终点位置添加一个虚拟石头sort(a+1,a+n+1);// 对石头位置进行排序memset(dp,0x3f,sizeof(dp));// 初始化dp数组为最大值dp[0]=0;// 起点位置（0位置）需要0次跳跃// 动态规划：计算到达每个石头的最少跳跃次数for(inti=1;i<=n+1;i++)// 遍历每个石头（包含终点）for(intj=0;j<i;j++)// 尝试从之前的石头j跳到石头i{if(a[i]-a[j]<=m)// 如果从石头j到石头i的距离不超过mdp[i]=min(dp[i],dp[j]+1);// 更新到达石头i的最少跳跃次数}// 调试用：输出每个石头的dp值// for (int i = 1; i <= n + 1; i++)// cout << dp[i] << " ";// cout << endl;cout<<dp[n+1]<<endl;// 输出到达终点的最少跳跃次数return0;}

【运行结果】

10 4 2 2 4 6 8 5