经常有点小迷糊 2021-08-25 09:22 采纳率: 96.7%
浏览 70
已结题

星际穿越这道题不会,给代码(C++)


题面描述
OICoderX同学刚刚参加完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。



数据范围
Nd 均为正数,则最大为105
  • 写回答

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);
        }
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 9月3日
  • 已采纳回答 8月26日
  • 创建了问题 8月25日

悬赏问题

  • ¥15 MATLAB动图的问题
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名