过桥【牛客tracker 每日一题】

过桥时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述d d dddd被困在了一个迷幻森林现在她面前有一条凶险的大河河中央有n nn个神奇的浮块浮块按1 ∼ n 1∼n1∼n顺序标号但两两并不相接第i ii个浮块上有一个数字a [ i ] a[i]a[i]可能是正数也可能是负数,每块浮块都附带一个魔法结界用于传送当a [ i ] a[i]a[i]为正数时d d dddd可以选择传送到第i k ( 1 ≤ k ≤ a [ i ] ) ik(1≤k≤a[i])ik(1≤k≤a[i])个浮块上,当d d dddd抵达n nn号浮块时才可以顺利脱身显然不管a [ n ] a[n]a[n]是多少都没有任何意义当a [ i ] a[i]a[i]为负时d d dddd只能选择标号小于等于i a [ i ] ia[i]ia[i]的任意一块浮块进行传送当i a [ i ] 1 ia[i]1ia[i]1时默认只能传送到1 11的位置每次传送都会花费1 s 1s1s的时间随着时间的流逝迷雾森林的空气会被逐渐榨干她现在在1 11号浮块她想知道她最快多久能顺利脱身如果始终无法逃脱请输出− 1 −1−1输入描述第一行一个数n ( 2 ≤ n ≤ 2000 ) n(2≤n≤2000)n(2≤n≤2000)接下来一行n nn个数a [ i ] ( 1 ≤ ∣ a [ i ] ∣ ≤ 2000 ) a[i](1≤|a[i]|≤2000)a[i](1≤∣a[i]∣≤2000)表示浮块上的数字输出描述输出一行表示对应的答案示例1输入4 2 2 -1 2输出2说明1 11跳到2 , 1 s 2,1s2,1s2 22跳到4 , 1 s 4,1s4,1s共2 s 2s2s示例2输入2 -1 -2输出-1解题思路本题本质是区间跳跃型最少步数问题核心利用「正数跳跃的连续性」推导出负数传送无优化价值最终通过动态规划求解最短路径。1. 核心性质负数传送不影响最优解正数传送的规则是从位置 i 可以跳到i1到ia[i]的所有连续位置。由此可以推出一个关键结论所有可达的浮块编号一定是从 1 开始的连续前缀。用数学归纳法可严格证明初始状态仅位置 1 可达满足连续前缀性质。归纳假设假设当前所有编号 ≤ r 的位置都可达。归纳推导遍历 1~r 中所有正数位置它们的跳跃范围会覆盖从 2 开始的连续区间最终新的最远可达位置 r’ 之前的所有位置必然全部可达连续性保持。因此任意可达位置 i所有编号小于 i 的浮块都一定可达且到达它们的步数 ≤ 到达 i 的步数。负数传送只能跳向编号更小的位置跳回后的步数为dp[i]1必然大于该位置原有的最少步数无法得到更优解。因此最优路径中永远不会使用负数传送可以直接忽略。2. 动态规划模型状态定义dp[i]表示到达第 i 个浮块所需的最少时间。初始状态dp[1] 0其余位置初始化为无穷大表示初始不可达。状态转移按编号从小到大遍历每个位置 i若 a[i] 0 且当前位置可达则枚举所有可跳到的后续位置j ∈ [i1, min(ia[i], n)]更新dp[j] min(dp[j], dp[i] 1)。结果判定若最终dp[n]仍为无穷大说明无法到达终点输出 -1否则输出dp[n]。算法时间复杂度为O ( n × max ⁡ ∣ a [ i ] ∣ ) O(n \times \max|a[i]|)O(n×max∣a[i]∣)本题 n ≤ 2000单步最大跳跃距离 2000总运算量约 400 万完全满足时间限制。总结核心逻辑通过正数跳跃的连续性证明负数传送无优化价值将问题简化为经典的最少跳跃次数问题通过线性动态规划逐点更新区间内的最少步数。关键操作可达前缀连续性推导、DP数组初始化、区间遍历更新最小值、不可达边界判定。效率保障数据规模较小暴力区间更新即可通过实现简洁直观不易出错。代码简要说明数组定义dp数组存储到达每个浮块的最少时间初始全部设为极大值 INFA数组存储每个浮块的传送数值。初始化起点 1 号浮块的时间设为 0其余初始为不可达状态。顺序DP转移从 1 到 n 遍历每个浮块若当前浮块数值为正则遍历所有能跳到的后续位置用当前步数 1 尝试更新目标位置的最少时间。结果输出判断终点 n 的 dp 值是否仍为无穷大是则输出 -1 表示无法逃脱否则输出最少时间。输入优化关闭流同步并解绑 tie提升输入输出效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll dp[30005],A[20005];ll n;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i){cinA[i];dp[i]INF;}dp[1]0;for(ll i1;in;i){if(A[i]0){for(ll ji1;jiA[i];j){dp[j]min(dp[i]1,dp[j]);}}}if(dp[n]INF)cout-1endl;elsecoutdp[n]endl;return0;}