过桥

NC229296. 过桥

描述

$dd$ 被困在了一个迷幻森林，现在她面前有一条凶险的大河，河中央有 $n$ 个神奇的浮块，浮块按 $1\sim n$ 顺序标号，但两两并不相接，第 $i$ 个浮块上有一个数字 $a[i]$ ，可能是正数，也可能是负数,每块浮块都附带一个魔法结界用于传送，当 $a[i]$ 为正数时， $dd$ 可以选择传送到第 $i+k(1≤k≤a[i])$ 个浮块上,当 $dd$ 抵达 $n$ 号浮块时才可以顺利脱身，显然不管 $a[n]$ 是多少，都没有任何意义，当 $a[i]$ 为负时， $dd$ 只能选择标号小于等于 $i+a[i]$ 的任意一块浮块进行传送，当 $i+a[i]<1$ 时，默认只能传送到 $1$ 的位置，每次传送都会花费 $1s$ 的时间，随着时间的流逝，迷雾森林的空气会被逐渐榨干，她现在在 $1$ 号浮块，她想知道，她最快多久能顺利脱身，如果始终无法逃脱，请输出 $-1$

输入描述

第一行一个数n(2≤n≤2000)
接下来一行n个数a[i](1≤|a[i]|≤2000)表示浮块上的数字

输出描述

输出一行，表示对应的答案

示例1

输入:

4
2 2 -1 2

输出:

说明:

1跳到2,1s
2跳到4,1s
共2s

示例2

输入:

2
-1 -2

输出:

-1

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 4ms, 内存消耗: 428K, 提交时间: 2021-11-05 19:56:24

#include<bits/stdc++.h>
using namespace std;
int n,a[2005],dp[2005];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	memset(dp,0x3f,sizeof(dp));
	dp[n]=0;
	for(int i=n-1;i>0;i--)
	{
		for(int j=1;j<=a[i];j++)
		dp[i]=min(dp[i],dp[min(n,i+j)]+1);
	}
	if(dp[1]>n)	dp[1]=-1;
	cout<<dp[1];
	return 0;
}

Python3 解法, 执行用时: 47ms, 内存消耗: 5788K, 提交时间: 2022-10-12 23:05:52

n = int(input())
a = list(map(int, input().split()))

l  , r , ans =  0 , 0 , 0

while r >= l:
    ans += 1
    newl = r + 1
    for p in range(l, r + 1):
        if p + a[p] >= n - 1:
            print(ans)
            exit()
        r = max(r, p + a[p])
    l = newl

print(-1)