46 lines
1.7 KiB
C++
46 lines
1.7 KiB
C++
#include<bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
/**
|
||
动态规划，设f[i]为到第i层的按键最少次数
|
||
*/
|
||
const int N = 100010;
|
||
const int INF = 0x3f3f3f3f;
|
||
int n; //n层楼
|
||
int a; //从a层
|
||
int B; //到b层
|
||
int K[N]; //k数组表示第一层出现的数字k[i]
|
||
int f[N]; //设f[i]为到第i层的按键次数最少(这个定义非常妙，最终的结果保存在f[b]里，
|
||
// 而f[b]是通过f[i]推导出来的)
|
||
/**
|
||
|
||
*/
|
||
int main() {
|
||
//初始化为INF
|
||
memset(f, 0x3f, sizeof f);
|
||
|
||
//读入
|
||
cin >> n >> a >> b;
|
||
for (int i = 1; i <= n; i++) cin >> k[i];
|
||
|
||
//base case,边界条件
|
||
f[a] = 0;
|
||
/******这个变量+循环尝试的方法很重要啊！******/
|
||
bool isLoop = true; //是否需要继续尝试，当本次操作没有修改时，就不需要继续操作了，
|
||
// 因为这就是无法再继续更新的意思。
|
||
while (isLoop) { //用这个循环控制，是最好理解的，而不是网上说的什么n次，那个n次是玄学，非科学
|
||
isLoop = false;
|
||
for (int i = 1; i <= n; i++) { //讨论在每一层楼时的情况
|
||
int x = i - k[i]; //下楼
|
||
int y = i + k[i]; //上楼
|
||
//如果下楼的步数优于现有解，那么优化掉
|
||
if (f[x] > f[i] + 1 && x >= 1) f[x] = f[i] + 1, isLoop = true;
|
||
//如果上楼的步数优于现有解，那么优化掉
|
||
if (f[y] > f[i] + 1 && y <= n) f[y] = f[i] + 1, isLoop = true;
|
||
}
|
||
}
|
||
//还是初始值的，表示无法到达！
|
||
if (f[b] == INF) cout << -1;
|
||
else cout << f[b]; // f[b]里保存的是结果
|
||
return 0;
|
||
} |