P3957 跳房子[二分答案][dp][单调队列]

朱雀 2021-12-22 15:52 214阅读 0赞

# P3957 跳房子 #

前年pj没去年难好吧

首先要发现这个答案是有单调性的。

这个很显然了：氪金越多游戏越容易玩，氪金越少越难。

然而也有界限：如果所有正数的和加起来还不够需求，无解。

所以二分答案，考虑如何判定答案。

是人都知道要设一个\\(dp\[i\]\\)表示跳前\\(i\\)个房子的最大分数。

50pts就很简单的暴力转移：

\\\[dp\[i\]=max(dp\[j\]+a\[i\]),j < i,lim\_1<dis\[i\]-dis\[j\] < lim\_2\\\]

其实很大的暗示了：把\\(a\[i\]\\)拿出来就是：\\(dp\[i\]=a\[i\]+max(dp\[j\])\\)

单调队列走一波，维护滑动窗口最大值！

--------------------

不得不说这里的单调队列很难写对。

我们弄一个指针\\(j\\)，当我们求\\(dp\[i\]\\)的时候就移动\\(j\\)到最近。

然后当我们询问最大值的时候再考虑讨论退役人员的弹出，得到最大值。

代码：

#include<bits/stdc++.h> using std::cin; using std::cout; using std::endl; #define ll long long const int maxn = 500005; const int INF = 0x8f8f8f8f; int a[maxn], dis[maxn]; int dp[maxn]; int n, d, k; std::deque<int> q;// dan diao di jian bool check(int g) { int lim1 = std::max(1, d - g), lim2 = d + g; memset(dp, 0x8f, sizeof dp); dp[0] = 0; q.clear(); int j = 0; for(int i = 1; i <= n; i++) { /*for(int j = 0; j < i; j++) { if(dis[i] - dis[j] >= lim1 && dis[i] - dis[j] <= lim2) { dp[i] = std::max(dp[i], dp[j] + a[i]); } }*/ while(j < i && dis[i] - dis[j] >= lim1) { if(dp[j] != INF) { while(!q.empty() && dp[q.back()] < dp[j]) q.pop_back(); q.push_back(j); } j++; } while(!q.empty() && dis[i] - dis[q.front()] > lim2) q.pop_front(); if(!q.empty()) dp[i] = dp[q.front()] + a[i]; } int ans = 0x8f8f8f8f; for(int i = 1; i <= n; i++) ans = std::max(ans, dp[i]);// wrong here return ans >= k; } int main() { cin >> n >> d >> k; dis[0] = a[0] = 0; for(int i = 1; i <= n; i++) { cin >> dis[i] >> a[i]; } int left = 0, right = std::max(dis[n], d), ans = -1; while(left <= right) { int mid = (left + right) >> 1; if(check(mid)) ans = mid, right = mid - 1; else left = mid + 1; } cout << ans << endl; return 0; }

转载于:https://www.cnblogs.com/Garen-Wang/p/10381444.html