题面描述
OICoder的X同学刚刚参加完NOI,成绩还得等几天才公布,趁着这个空档,决定给自己放个小假,允许自己玩1小局游戏。
他打开了他的《星际穿越0202》,在该游戏中,有一片广袤无垠的宇宙,其包含N个虫洞,编号分别为1~N,且这些虫洞依次分布在一条直线上。
在游戏设定下,每个虫洞具备空间跳跃能力d,代表其往前跳跃的虫洞数。举个例子,若第1个虫洞的跳跃能力为3,那么从第1个虫洞可以跳跃到第2个、第3个、第4个。
现在他在站在第1个虫洞,也知道每个虫洞的空间跳跃能力d,游戏目标是到达第N个虫洞。他准备写个程序计算出到达第N个虫洞的最少跳跃次数。
(他已经在写了,你也来写一个吧~)
输入格式
第1行输入虫洞数N。
接下来的N行,第i行输入第i个虫洞的空间跳跃能力d。
输出格式
输出从第1个虫洞到达第N个虫洞的最少跳跃次数
输入样例
5
2
3
2
2
4
输出样例
2
样例解释
跳到最后一个位置的最小跳跃数是2。
第1次跳跃:从虫洞1跳到虫洞2。
第2次跳跃:从虫洞2跳到虫洞5。
数据范围
N、d 均为正数,则最大为105
星际穿越这道题不会,给代码(C++)
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- larwar 2021-08-25 11:52关注
这个应该可以吧
#include <iostream> using namespace std; int n,a[10001],ans = 9999; void dump(int x,int t); int main(){ cin >> n; for (int i=0;i<n;i++){ cin >> a[i]; } dump(0,0); cout << ans << endl; } void dump(int x,int t){ if (x >= n-1){ ans = min(t,ans); return; } int fx = a[x]; t++; for (int i=1;i<=fx;i++){ dump(x+i,t); } }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 使用ue5插件narrative时如何切换关卡也保存叙事任务记录
- ¥20 软件测试决策法疑问求解答
- ¥15 win11 23H2删除推荐的项目,支持注册表等
- ¥15 matlab 用yalmip搭建模型,cplex求解,线性化处理的方法
- ¥15 qt6.6.3 基于百度云的语音识别 不会改
- ¥15 关于#目标检测#的问题:大概就是类似后台自动检测某下架商品的库存,在他监测到该商品上架并且可以购买的瞬间点击立即购买下单
- ¥15 神经网络怎么把隐含层变量融合到损失函数中?
- ¥15 lingo18勾选global solver求解使用的算法
- ¥15 全部备份安卓app数据包括密码,可以复制到另一手机上运行
- ¥20 测距传感器数据手册i2c