写了好久，感觉自己好菜，唉……
首先发现这个$g$的取值具有单调性，可以想到二分答案，然后考虑用$dp$来检验，这样子可以写出朴素的转移方程：
设$f_i$表示以$i$结尾的最大价值，那么有$f_i = max(f_j) + val_i$ $(0 < j < i)$ $((dis_i - (d + g) \leq dis_j \leq dis_i - max(d - g, 1)))$。
然后注意到是选取一个滑动窗口的最大值，用一个单调队列优化一下就可以了。
时间复杂度$O(nlogn)$。
注意开$long\ long$。
Code：
#include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int N = 5e5 + 5; const ll inf = 1LL << 60; int n, d, dis[N], q[N]; ll cur, val[N], f[N]; template <typename T> inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > ‘9‘ || ch < ‘0‘; ch = getchar()) if(ch == ‘-‘) op = -1; for(; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } template <typename T> inline void chkMax(T &x, T y) { if(y > x) x = y; } template <typename T> inline int max(T x, T y) { return x > y ? x : y; } inline bool chk(int mid) { int st = max(1, d - mid), ed = d + mid, l = 1, r = 0; memset(f, 0LL, sizeof(f)); for(int j = 0, i = 1; i <= n; i++) { for(; j < i && dis[j] <= dis[i] - st; j++) { for(; l <= r && f[q[r]] < f[j]; --r); q[++r] = j; } for(; l <= r && dis[q[l]] < dis[i] - ed; ++l); ll mx = f[q[l]]; if(l > r) mx = -inf; f[i] = mx + val[i]; if(f[i] >= cur) return 1; } return 0; } /*inline bool chk(int mid) { int st = max(1, d - mid), ed = d + mid; memset(f, 0, sizeof(f)); for(int i = 1; i <= n; i++) { int res = -inf; for(int j = 0; j < i; j++) if(dis[j] >= dis[i] - ed && dis[j] <= dis[i] - st) chkMax(res, f[j]); f[i] = res + val[i]; if(f[i] >= cur) return 1; } return 0; } */ int main() { read(n), read(d), read(cur); int mn = 0; ll sum = 0; for(int i = 1; i <= n; i++) { read(dis[i]), read(val[i]); chkMax(mn, dis[i]); if(val[i] > 0) sum += val[i]; } if(sum < cur) return puts("-1"), 0; int ln = 0, rn = mn, mid, res = -1; for(; ln <= rn; ) { mid = (ln + rn) / 2; if(chk(mid)) rn = mid - 1, res = mid; else ln = mid + 1; } printf("%d\n", res); return 0; }
原文：https://www.cnblogs.com/CzxingcHen/p/9826578.html
