【线段树】Frog Traveler（CF751D）

本文主要是介绍【线段树】Frog Traveler（CF751D），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

CF751D

---

题目大意

现在有n个点，当你在i时，可以向前跳 $0\sim a_i$ 步，跳到j，然后向后走$b_j$步，现在让你从n开始跳，回答跳到0的最少步数

---

解题思路

设$f_i$为跳到i的最少步数，每次转移先减$b_i$然后再转移

求最小值可以用线段树优化

时间复杂度 $O(nlogn)$

---

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 300300
using namespace std;
int n,now,v[N],a[N],b[N],lst[N];
struct Tree
{#define ls x*2#define rs x*2+1int s[N<<2],lazy[N<<2];void push_up(int x){if(v[s[ls]]<v[s[rs]])s[x]=s[ls];//因为要存路径，所以更改存的方式else s[x]=s[rs];return;}void get(int x,int y){if(v[s[x]]>v[y])s[x]=y;if(v[lazy[x]]>v[y])lazy[x]=y;return;}void build(int x,int l,int r){s[x]=lazy[x]=n+2;if(l==r)return;int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);return;}void push_down(int x){if(lazy[x]!=n+2){get(ls,lazy[x]);get(rs,lazy[x]);lazy[x]=n+2;}return;}void add(int x,int L,int R,int l,int r,int y){if(L==l&&R==r){get(x,y);return;}push_down(x);int mid=L+R>>1;if(r<=mid)add(ls,L,mid,l,r,y);else if(l>mid)add(rs,mid+1,R,l,r,y);else add(ls,L,mid,l,mid,y),add(rs,mid+1,R,mid+1,r,y);push_up(x);}int ask(int x,int l,int r,int y){if(l==r)return s[x];push_down(x);int mid=l+r>>1;if(y<=mid)return ask(ls,l,mid,y);else return ask(rs,mid+1,r,y);}
}T;
void dfs(int x)
{if(x==n)return;dfs(lst[x]);printf("%d ",x-1);
}
int main()
{scanf("%d",&n);n++;for(int i=2;i<=n;++i)scanf("%d",&a[i]);for(int i=2;i<=n;++i)scanf("%d",&b[i]);T.build(1,1,n);v[n+2]=1e9;v[n+1]=0;T.add(1,1,n,n,n,n+1);for(int i=n;i>1;--i){lst[i]=T.ask(1,1,n,i);v[i]=v[lst[i]]+1;now=i+b[i];//往后bi步T.add(1,1,n,now-a[now],now,i);}lst[1]=T.ask(1,1,n,1);v[1]=v[lst[1]]+1;if(lst[1]==n+2){puts("-1");return 0;}printf("%d\n",v[1]-1);now=1;dfs(1);return 0;
}

这篇关于【线段树】Frog Traveler（CF751D）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---