邢台做wap网站的公司,seo如何快速排名百度首页,推荐网址,行业类网站应如何建设正题
CF751D 题目大意
现在有n个点#xff0c;当你在i时#xff0c;可以向前跳 0∼ai0\sim a_i0∼ai 步#xff0c;跳到j#xff0c;然后向后走bjb_jbj步#xff0c;现在让你从n开始跳#xff0c;回答跳到0的最少步数 解题思路
设fif_ifi为跳到i的最少步数…正题
CF751D 题目大意
现在有n个点当你在i时可以向前跳 0∼ai0\sim a_i0∼ai 步跳到j然后向后走bjb_jbj步现在让你从n开始跳回答跳到0的最少步数 解题思路
设fif_ifi为跳到i的最少步数每次转移先减bib_ibi然后再转移
求最小值可以用线段树优化
时间复杂度 O(nlogn)O(n\ log\ n)O(n log n) code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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*21int s[N2],lazy[N2];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]n2;if(lr)return;int midlr1;build(ls,l,mid);build(rs,mid1,r);return;}void push_down(int x){if(lazy[x]!n2){get(ls,lazy[x]);get(rs,lazy[x]);lazy[x]n2;}return;}void add(int x,int L,int R,int l,int r,int y){if(LlRr){get(x,y);return;}push_down(x);int midLR1;if(rmid)add(ls,L,mid,l,r,y);else if(lmid)add(rs,mid1,R,l,r,y);else add(ls,L,mid,l,mid,y),add(rs,mid1,R,mid1,r,y);push_up(x);}int ask(int x,int l,int r,int y){if(lr)return s[x];push_down(x);int midlr1;if(ymid)return ask(ls,l,mid,y);else return ask(rs,mid1,r,y);}
}T;
void dfs(int x)
{if(xn)return;dfs(lst[x]);printf(%d ,x-1);
}
int main()
{scanf(%d,n);n;for(int i2;in;i)scanf(%d,a[i]);for(int i2;in;i)scanf(%d,b[i]);T.build(1,1,n);v[n2]1e9;v[n1]0;T.add(1,1,n,n,n,n1);for(int in;i1;--i){lst[i]T.ask(1,1,n,i);v[i]v[lst[i]]1;nowib[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]n2){puts(-1);return 0;}printf(%d\n,v[1]-1);now1;dfs(1);return 0;
}
