# [洛谷 3957][NOIP 2017 普及T4] 跳房子【二分答案+DP+单调队列优化】

• 2018-01-23
• 0
• 0

## 输入输出样例

```7 4 10
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2```

`2`

```7 4 20
2 6
5 -3
10 3
11 -3
13 1
17 6
20 2```

`-1`

## Solution:

。。还好今年考了提高组，否则要跪。。再这样下去，似乎明年普及要考网络流了。。

• dp[ i ] = max{ dp[ j ] } + s[ i ]，其中 j < id - g ≤ x[ i ] - x[ j ] ≤ d + g

## Code: O(nlogxn) [11183KB, 836MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

int n, d;
int x[500010], s[500010];
ll k, dp[500010];
int q[500010], fr, re;  // Maintain a decreasing sequence

inline bool check(int g){
memset(dp, 0xc0, sizeof(dp)), dp[0] = 0;
fr = re = 1, q[0] = -1;  // Begin with an empty queue, q[0] is the sentry
for(register int i = 1; i <= n; i++){
while(q[re - 1] + 1 < i && x[q[re - 1] + 1] + d - g <= x[i]){  // The new ones are far enough
int cur = q[re - 1] + 1;
while(fr != re && dp[cur] >= dp[q[re - 1]]) re--;  // Pop the farther and smaller ones
q[re++] = cur;
}
while(fr != re && x[q[fr]] + d + g < x[i]) fr++;  // The largest ones are too far away
if(fr != re) dp[i] = dp[q[fr]] + s[i];
if(dp[i] >= k) return 1;
}
return 0;
}

int main(){
scanf("%d%d%lld", &n, &d, &k);
for(register int i = 1; i <= n; i++)
scanf("%d%d", x + i, s + i);
int l = 0, r = x[n] - d + 1;
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(l <= x[n] - d) printf("%d\n", l);
else puts("-1");
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai