Noip2017跳房子(普及t4)


本文总阅读量
Posted by yjjr's blog on February 6, 2018

T4

题面传送门

感觉在pj组放这道题是不是有些难了,难度大于NOIP2015D2T1那道跳石子

老套路先二分答案+DP

f[i]表示跳前i个格子,且停在第i个格子最大分数;

sc[i]表示第i个格子的分数。

转移:f[i]=max(f[j])+sc[i] 前提是从j可以跳到i

显然,这种时间复杂度太大

需要再次使用单调队列优化

发现转移中j的位置是随着i的右移而右移的

对于格子j,如果dis[i]-dis[j]>=机器人能跳的最小距离,显然f[j]是可以进队的

但是要维护整个队列单调递减,每次直接去队头就好了

注意要把最小值置极小,否则会WA

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const ll maxn=5e5+6,inf=1844387848000;
ll dis[maxn],sc[maxn],f[maxn],n,d,k,x,y;
bool check(int x)
{
    deque<ll>que;
    ll from=0,stepl=max(d-x,(ll)1),stepr=d+x;
    rep(i,1,n){
        while(dis[from]+stepl<=dis[i]){
            while(!que.empty()&&f[que.back()]<=f[from])que.pop_back();
            que.push_back(from++);
        }
        while(!que.empty()&&dis[que.front()]+stepr<dis[i])que.pop_front();
        if(!que.empty())f[i]=f[que.front()]+sc[i];
        else f[i]=-inf;
        if(f[i]>=k) return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>d>>k;
    ll sum=0;
    rep(i,1,n){
        cin>>x>>y;
        dis[i]=x;sc[i]=y;
        if(y>0)sum+=y;
    }
    if(sum<k){cout<<"-1\n";return 0;}
    int l=1,r=dis[n],mid;
    while(l<r){
        mem(f,0);
        mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}
    
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr