每日一题C++版(袋鼠过河)

编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化和锻炼自己的编程能力(最起码不会忘记编程)

特别说明:编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法,所以提供的代码不一定是最优解,但是本文提供的编程代码均为通过测试代码。

袋鼠过河

题目描述

一只袋鼠要从河这边跳到河对岸,河很宽,但是河中间打了很多桩子,每隔一米就有一个,每个桩子上都有一个弹簧,袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同,用一个数字代表它的力量,如果弹簧力量为5,就代表袋鼠下一跳最多能够跳5米,如果为0,就会陷进去无法继续跳跃。河流一共N米宽,袋鼠初始位置就在第一个弹簧上面,要跳到最后一个弹簧之后就算过河了,给定每个弹簧的力量,求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出“-1”

输入描述:

输入分两行,第一行是数组长度N (1 ≤ N ≤10000),第二行是每一项的值,用空格分隔。

输出描述:

输出最少的跳数,无法到达输出-1

示例

输入

5

2 0 1 1 1

输出

4

解析

本题是一个动态规划的问题,当然也可以用dp[]来实现。小白为大家提供了两种解决方案,不过后一种并没有考虑如何判定不能到达的情况,请小伙伴们可以自己思考一下。好了,首先讲解一下我们的思路。我们从后往前想,当我站在某处的时候,一定希望是最远的弹簧跳过来的,这样我们就判定我们前面的弹簧距离我们的位置和它本身的弹力,寻找到离我们最远的(程序中也就是从前完后的第一个能跳到该位置的弹簧),如果没有找到,就是无法跳过河。放我们找到最远的弹簧之后,便寻找能跳到那个弹簧上的最远的弹簧直到遇到第一个弹簧。

注释掉的是采用dp[]思路去解决的,感兴趣的小伙伴可以尝试一下。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
 vector<int> fox;
 Solution(){};
 int step(int i)
 {
   for (int j = 0; j < i; j++)
   {
     if (fox[j]>=(i-j))//从左找最远的能跳到当前位置的号码
     {
       return j;
     }
   }
   return -1;
 }

private:

};
int main()
{
 int index;
 while (cin>>index)
 {
   vector<int> fox;
   for (int i = 0; i < index; i++)
   {
     int f;
     cin >> f;
     fox.push_back(f);
   }
   int step=0;
   int current = fox.size();
   Solution solution;
   solution.fox = fox;
   while (current!=0)
   {
     current = solution.step(current);
     if (current==-1)
     {
       cout << "-1" << endl;
       return 0;
     }
     step++;
   }
   cout << step << endl;
 }
 return 0;
}
//int main()
//{
//  int index;
//  while (cin >> index)
//  {
//    vector<int> fox;
//    for (int i = 0; i < index; i++)
//    {
//      int f;
//      cin >> f;
//      fox.push_back(f);
//    }
//    vector<int> step(fox.size() + 1, fox.size() + 1);
//    step[0] = 0;
//    for (int i = 0; i < fox.size(); i++)
//    {
//      for (int j = 1; j <= fox[i]; j++)
//      {
//        if (i + j >= step.size())
//        {
//          break;
//        }
//        step[i + j] = min(step[i + j], step[i] + 1);
//      }
//    }
//    cout << *(--step.cend()) << endl;
//  }
//  return 0;
//}

运行结果

(0)

相关推荐

  • [CF208E] Blood Cousins - dsu on tree, LCA

    [CF208E] Blood Cousins - dsu on tree, LCA Description 给你一片森林,每次询问一个点与多少个点拥有共同的 K 级祖先. Solution dsu o ...

  • c 如何求任意多边形的面积

    #include <iostream> #include <vector> using namespace std; struct Point//定义坐标结构体 { float ...

  • 浙大版《数据结构(第2版)》题目集-习题8.2

    习题8.2 银行排队问题之单队列多窗口加VIP服务 (30point(s)) 假设银行有K个窗口提供服务,窗口前设一条黄线,所有顾客按到达时间在黄线后排成一条长龙.当有窗口空闲时,下一位顾客即去该窗口 ...

  • C++面向对象程序设计 笔记整理(1)——编程基础

    字符与字符串 大小写转换 void lower_or_upper_case(char c) { int transferred_c; if ( ('a'<=c) && (c< ...

  • 【黑客数学·每日一题】暑假期间“每日一题”汇总版

    各位黑客伙伴们: 大家好!随着暑期的结束,我们迎来了崭新的学期,"每日一题"的发布时间也正式恢复为常规的每周一到周五的下午(一周五期). 有部分黑客伙伴们在暑假安排了各种各样精彩活 ...

  • 每日一题 C++版(走迷宫)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(汽水瓶)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(简单密码)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(分类有效的IP地址和掩码)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(坐标移动)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(组成最大的数)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(电话号码分身)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(区间合并)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...