题解 P3957 【跳房子】

题目链接

Solution 跳房子

单调队列

---

分析：显而易见答案具有单调性，因为花费金币越多机器人越灵活，花费金币少的可行决策是花费金币多的可行决策的子集

我们可以二分一个答案\(ans\)，如果\(O(n^2)\)做\(dp\)的话可以得到\(50\)分

对于任意一个位置，它能转移的位置都在一段区间内，由于每个格子位置单调递增，可行转移状态集合类似于滑动窗口，可以用单调队列来维护，做到\(O(n)dp\)

注意初始值

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 5e5 + 100;
typedef long long ll;
struct Node{
    int pos,val;
}val[maxn];
int q[maxn],head,tail,n,d,k,l = 0,r = 1e9,ans = -1;
ll f[maxn];
inline bool check(int g){
    int l = max(d - g,1),r = d + g,pos = 0,head = 1,tail = 0;
    for(int i = 1;i <= n;i++)f[i] = -1e13;
    for(int i = 1;i <= n;i++){
        while(pos < i && val[pos].pos <= val[i].pos - l){
            while(head <= tail && f[q[tail]] <= f[pos])tail--;
            q[++tail] = pos++;
        }
        while(head <= tail && val[q[head]].pos < val[i].pos - r)head++;
        if(head <= tail)f[i] = f[q[head]] + val[i].val;
    }
    for(int i = 1;i <= n;i++)
        if(f[i] >= k)return true;
    return false;
}
int main(){
    scanf("%d %d %d",&n,&d,&k);
    for(int i = 1;i <= n;i++)
        scanf("%d %d",&val[i].pos,&val[i].val);
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid))ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    printf("%d\n",ans);
    return 0;
}