NC21848. Problem F. Jhadgre的伤心地
描述
Jhadgre为了他的女神，准备了一场盛大的告白，可惜却被女神毫不留情的拒绝。于是Jhadgre决定离开这个伤心之地。但是钱都被Jhadgre拿去准备告白了，剩下的钱并不够他买车票，只够他坐公交车。
Jhadgre所在城市的所有公交车站总体来说都在一条直线上，在这里有两种公交车，一种是全城公交，这种公交车在城市的任何一站都可以上下车，付了车费后，从当前站开始，最多可以向后坐5站（即从第i站上车，可以选择在第i+1,i+2,i+3,i+4,i+5站下车）。还有一种是区间公交，也就是可以在第X站上车，直到第Y站(X<Y)，中途每一站都可以下车但不可以上车。所有公交车的上车费都是2元。
现在Jhadgre为了最快的逃离这个伤心地，他决定不管上哪种公交车，只要上去了，就一定坐到底再下车，中途不会下车，并且他现在所在的地点为第1站，他认为要到第N站以后的站，他才算彻底逃离这个伤心地。
现在Jhadgre想知道他手里的钱够不够逃离这个伤心地，你可以帮他计算一下他最少需要花多少钱才能离开这个伤心地吗？
输入描述
只包含一组数据。
第一行一个整数N，意义如题（10<=N<=100）
接下去一行中共N个整数a1,a2,a3...aN，由空格隔开,ai表示第i站的区间公交能到达第ai站，保证(i<ai)
输出描述
Jhadgre最少需要花的钱
示例1
输入:
10 7 11 4 5 6 7 8 9 10 11
输出:
4
说明:
以下给出两种乘车方案：C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 480K, 提交时间: 2018-12-29 17:04:46
#include<bits/stdc++.h>
using namespace std;
int n,a[105];
int step(int x){
if(x > n) return 0;
else return min(step(a[x]),step(x + 5)) + 1;
}
int main(){
cin>>n;
for(int i = 1; i <= n;i++)
cin>>a[i];
cout<<step(1) * 2<<endl;
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 432K, 提交时间: 2022-02-18 14:06:59
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+5];
for(int i=0;i<n;i++)
cin>>a[i];
int x=0;
int res=0;
while(x<n)
{
x=max(a[x],x+5);
res+=2;
}
cout<<res;
}