F 过桥

题意

有n个 方块，每一个方块都一个数$a_{i}a\_\{i\}$ ,为正数可以往前跳，跳到 $ii$ 到 $i+a[i]i+a[i]$，负数可以往回跳 可以跳到$11$到 $i+a[i]i+a[i]$。

思路

这个题目有很明显的转移，且数据范围较小，可以采用动态规划。 假设 $dp[i]dp[i]$ 表示到达第 i 个方块的最短用时。由于负数相当于往回走，用时肯定更长，负数肯定可以直接跳过，有负数可能导致不能遍历到第 n 个 方块，如果可以遍历到第 n 个方块直接输出 $dp[n]dp[n]$ ,如果不能输出 -1 ；

• 转移方程：

dp[i+a[i]]=min(dp[i]+1,dp[i+a[i]);

负数直接跳过

• code

#include<bits/stdc++.h>
using namespace std;
int dp[30000],a[20000];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],dp[i]=INT_MAX;
    dp[1]=0;
    for(int i=1;i<=n;i++){
        if(a[i]>0){
            for(int j=i+1;j<=i+a[i];j++){
                dp[j]=min(dp[i]+1,dp[j]);
            }
        }
    }
    if(dp[n]==INT_MAX) cout<<-1<<endl;
    else cout<<dp[n]<<endl;
}