题目描述
期末考试终于结束了。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 人正在系统学习中
