洛谷P3957：跳房子—

https://www.luogu.org/problem/P3957

沉迷普及组题无法自拔。

显然二分答案，然后里面套个dp，$f[i]$表示跳到第$i$个格子的最大得分，复杂度$O(n^2logn)$50pts到手。

但是仔细思考就知道$f[i]$只能从它前面一段特定区域的最大的$f$转移过来，并且这个区域是随着$i$往后动的。

滑动窗口石锤，我们就可以维护一个单调队列来做这道题了，复杂度直接变为$O(nlogn)$

……但是即使你想出来了实现也不好写，而且仍然有很多细节需要解决……debug细节花了一个小时多……老龄化实锤。

1.这题只能跳到给定的方块上（最开始我想复杂了结果觉得不可做看了题解才意识到……）

2.注意我们要转移的对象和我们的滑动窗口是有一定距离的，也就是说转移$f[i]$时$f[i-1]$不一定在滑动窗口里，我们就需要另开变量去找哪些在滑动窗口里，详见代码。

3.注意初始化！到不了的格子别忘记初始为-INF，INF要特别大，必要时开long long

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=5e5+;

const ll INF=1e12;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct data{

    int x;

    ll s;

}q[N],f[N];

int n,d,k;

int x[N],s[N];

bool pan(int g){

    ll ans=;int l=,r=;

    q[++r]=(data){,};

    for(int i=,j=;i<=n;i++){

        f[i].s=-INF;

        if(d-g>x[i])continue;

        while(l<=r&&(q[l].x+d+g<x[i]))l++;

        for(;j<i;j++){

            if(f[j].x+d+g<x[i])continue;

            if(f[j].x+d-g>x[i])break;

            while(l<=r&&f[j].s>=q[r].s)r--;

            q[++r]=f[j];

        }

        if(l<=r){

            f[i]=(data){x[i],q[l].s+s[i]};

            ans=max(ans,f[i].s);

        }

    }

    return ans>=k;

}

int main(){

    n=read(),d=read(),k=read();

    for(int i=;i<=n;i++){

        x[i]=read();s[i]=read();

    }

    int l=,r=1e9;

    while(l<r){

        int mid=(l+r)>>;

        if(pan(mid))r=mid;

        else l=mid+;

    }

    if(pan(l))printf("%d\n",l);

    else puts("-1");

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

洛谷P3957：跳房子——题解

最新文章

热门文章