cf?crossfire!
Frog Traveler CodeForces - 1601B
题意：有一只井底之蛙，井深度为n < 3e5，对于每个深度i，最多可以跳ai步，当从一个位置跳到i后，会滑下去bi步。问最少跳多少步可以跳到地面（即i=0)
·
·
·
·
·
·
··
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
··
·
·
思路：dp，令dp[ i ]=跳到i位置所需要的最少步数。假设从i位置开始跳，i位置能跳到的集合为s=[ i,i-a[ i ] ];所以dp[ j ]=min(dp[ i ]+1,dp[ j ]),j属于s。
由于每次更新的区间是一段连续的区间，所以我们可用线段树维护区间最小值。复杂度O(n * logn)。
其实还有O(n)的做法，方法就是，我们不妨从最低点开始跳。那么可以得到一段连续的区间的dp值都为1。对于这一段区间，我们只要找到这段区间能跳到的最高点，那么从最高点到这段区间的dp值都为2，依次类推。就像双指针的操作了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=3e5+11;
ll ar[maxn],br[maxn],c[maxn];
ll n;
vector<ll> path;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(ll i=1;i<=n;i++) cin>>ar[i];
for(ll i=1;i<=n;i++) cin>>br[i];
for(ll i=1;i<=n;i++) c[i]=i+br[i];
ll l=n,h=n-ar[n];
ll ans=0;
while(l>=h && h>0){
ll minn=INF,v;
for(ll i=l;i>=h;i--){
if(c[i]-ar[c[i]]<minn){
minn=c[i]-ar[c[i]];
v=i;
}
}
path.push_back(v);
l=h-1,h=minn;
ans++;
}
if(h>0) cout<<-1<<endl;
else{
cout<<ans+1<<endl;
for(auto i=path.begin();i!=path.end();i++) cout<<*i<<" ";
cout<<0;
}
return 0;
}
|