新飞行棋——动态规划

简介: 题目描述期末考试终于结束了。Andy同学感觉松了一口气,他决定重温小时候的快乐时光–下飞行棋。但是他弄丢了传统飞行棋需要的骰子,因此他发明了一种新型的飞行棋游戏,规则如下:棋盘上有n个格子,由近到远分别编号为1到n。对于1<=i<=n,第i个格子上写着一个正整数Ni。当玩家处于第a个格子时,他可以选择往后走Na步,或者往前倒退Na步。当然如果Na+a>n,那么他就只能选择后退;同理如果a-Na<1,那么他就只能选择前进。保证不会出现既不能前进又不能后退的格子。Andy学完编程后对一个问题很感兴趣:从编号s出发,至少需要经过几把,可以到达t点?(例如在a点选择往前走Na步,称之为一把)。

题目描述


期末考试终于结束了。Andy同学感觉松了一口气,他决定重温小时候的快乐时光–下飞行棋。

但是他弄丢了传统飞行棋需要的骰子,因此他发明了一种新型的飞行棋游戏,规则如下:棋盘上有n个格子,由近到远分别编号为1到n。对于1<=i<=n,第i个格子上写着一个正整数Ni。当玩家处于第a个格子时,他可以选择往后走Na步,或者往前倒退Na步。当然如果Na+a>n,那么他就只能选择后退;同理如果a-Na<1,那么他就只能选择前进。保证不会出现既不能前进又不能后退的格子。

Andy学完编程后对一个问题很感兴趣:从编号s出发,至少需要经过几把,可以到达t点?(例如在a点选择往前走Na步,称之为一把)。


输入


第一行三个整数,分别为n,s,t意义如题面所述。

第二行n个正整数,第i个数为Ni。


输出


一个数,为最少经过的把数。如果s无法到达t,输出-1。


样例输入 Copy


6 6 4
1 2 2 3 1 2


样例输出 Copy


1


提示


对于前10%的数据,s=t;

对于前40%的数据,n<=200;

对于另外10%的数据,s无法到达t;

对于100%的数据,n<=200000;


#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define wuyt main
typedef long long ll;
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
if(c == '-')Nig = -1,c = getchar();
while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
return Nig*x;}
#define read read()
const ll inf = 1e15;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
///ll n,m,k,x;
/**
ll superpow(ll a,ll b){
    ll ans=1;
    while (a>0)
    {
        if (a%2) ans=ans*b%n;
        b=b%n*b%n;
        a/=2;
    }
    return ans;
}
ll n,x;**/
ll num[maxn];
ll dp[maxn];
int main(){
    ll n=read,s=read,t=read;
    for(int i=1;i<=n;i++) num[i]=read;
    dp[s]=1;int flg=1;
    while(flg){
        flg=0;
        for(int i=1;i<=n;i++){
            if(dp[i]){
                if(i-num[i]>=1)///back
                {
                    if(dp[i-num[i]]==0||dp[i-num[i]]-1>dp[i]){
                        flg=1;
                        dp[i-num[i]]=dp[i]+1;
                    }
                }
                /**
                向后走的情况,后面的一种的方法数量等于在前面那一步的方法数加一
                有办法走,就将flg->1;
                **/
                if(i+num[i]<=n)///front
                {
                    if(dp[i+num[i]]==0||dp[i+num[i]]>dp[i]+1){
                        dp[i+num[i]]=dp[i]+1;
                        flg=1;
                    }
                }
                /**
                向前走的情况,前面的一种方法数量等于后面的方法数量加上1
                在这种情况下,就需要将flg->1
                **/
            }
        }
    }
    printf("%lld\n",dp[t]-1);
    return 0;
}

思路来自同学:https://me.csdn.net/weixin_45675097


文章知识点与官方知识档案匹配,可进一步学习相关知识

算法技能树leetcode-动态规划22-括号生成6831 人正在系统学习中

目录
相关文章
|
17天前
|
C++ NoSQL 容器
动态规划三
动态规划三
|
17天前
|
C++ NoSQL 容器
动态规划二
动态规划二
|
17天前
|
机器人 NoSQL 容器
动态规划一
动态规划一
|
4天前
|
存储 JavaScript 机器人
动态规划问题
动态规划问题
10 0
|
17天前
动态规划1
动态规划1
16 0
动态规划1
|
9月前
|
存储
【动态规划】
【动态规划】
|
17天前
动态规划
动态规划
27 0
|
12月前
|
定位技术
动态规划题:夺宝奇兵
动态规划题:夺宝奇兵
51 0
|
人工智能
动态规划的证明题
动态规划的证明题
|
存储
动态规划最大字段和
动态规划最大字段和
71 0

热门文章

最新文章