D. Frog Traveler
考虑dp
dp[i]表示i高度的时候最少多少步能达到
然后再bfs就可以了 但是这样是n2的 虽然看起来只有n个点
我们考虑优化
我们主要复杂度是当前点 还会去搜索其他已经入队的点
这样怎么办呢 我们可以维护一个set 要是已经入队的点 我们就不用去搜索了
我们直接二分出一个没搜索过的 并且合法的 然后给她erase掉就表示他搜过了
int x = *s.lower_bound(u - a[u]);
if (u < x)break;
s.erase(x);
然后就是更新
int v=x+b[x];
if(dp[v]>dp[u]+1){
dp[v]=dp[u]+1;
pre[v]={u,x};
q.push(v);
}
最后是输出路径 我们记录一个pre数组就是了 但是这里记录的不是出发点 而是到达点 所以我们要多记录一个
int x=0;
vector<int>ans;
while(x!=n){
ans.push_back(pre[x].second);
x=pre[x].first;
}
cout<<ans.size()<<endl;
reverse(all(ans));
for(auto i:ans)cout<<i<<' ';cout<<endl;
完整代码
void solve() {
int n;cin>>n;
vector<int>a(n+10),b(n+10),dp(n+10);
vector<pair<int,int>>pre(n+10);
set<int>s;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=0;i<=n+1;i++)dp[i]=INF,s.insert(i);
queue<int>q;
q.push(n);
dp[n]=0;
while(q.size()){
auto u=q.front();q.pop();
while(1) {
int x = *s.lower_bound(u - a[u]);
if (u < x)break;
s.erase(x);
int v=x+b[x];
if(dp[v]>dp[u]+1){
dp[v]=dp[u]+1;
pre[v]={u,x};
q.push(v);
}
}
}
if(dp[0]==INF)cout<<-1<<endl;
else {
int x=0;
vector<int>ans;
while(x!=n){
ans.push_back(pre[x].second);
x=pre[x].first;
}
cout<<ans.size()<<endl;
reverse(all(ans));
for(auto i:ans)cout<<i<<' ';cout<<endl;
}
}
标签:pre,10,751,int,Codeforces,while,push,Div,dp
From: https://www.cnblogs.com/ycllz/p/16860011.html