[题]跳房子 #单调队列优化(伪)

题目

洛谷——P3957 [NOIP2017 普及组] 跳房子
ACwing——472. 跳房子

题意：
花最少的金币，获得分数k。
花g个金币可以升级机器人，使其跳跃距离范围向上向下增加g。
求满足分数下，最少使用金币数。

---

题解

1. 普通写法：贪心直接剪枝。
   这是个取巧的办法。也许数据再强一点就过不了了。
   但是很好想、好写。

2. 优化写法：单调队列优化。
   跳转博客：[题] 跳房子 #dp #二分 #单调队列优化

---

代码

#include 
#define INF 0x7f7f7f7f
using namespace std;
typedef long long LL;
const int N = 500010;
int n, d, k;
//f[i]是指到i点能获得的最高分。
LL dist[N], w[N], f[N];
//检查花费g个金币进行改造后，最高得分是否会超过k。
bool check(int gold) {
    //机器人能够弹跳的范围[L,R]
    int L = max(1, d - gold);
    int R = d + gold;
    //注意：这里要初始化为负无穷
    for(int i = 1; i <= n; i ++)
    	f[i] = -INF;
    f[0] = 0;
    //目的格子
    for(int i = 1; i <= n; i ++) {
    	//要用单调队列优化的话，就是优化掉枚举j的过程。 
        //从i的前一个格子开始，向前枚举格子j
        for(int j = i - 1; j >= 0; j --) {
            //剪枝：如果机器人从j号格子加上R还是无法到达i号格子，那么从j号格子之前的格子也无法到达i号格子
            if(dist[j] + R < dist[i]) 
                break;
            //机器人从j号格子加上L还是超过了i号格子，那么继续尝试j号之前的格
            if(dist[j] + L > dist[i]) 
                continue;
            //能到这一步说明可以从j号格子跳到i号格子。
            f[i] = max(f[i], f[j] + w[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("%lld%lld", &dist[i], &w[i]);
    //R的大小可以通过x/n来确定，平均距离为2000
    int L = 0, R = 20000, ans = -1;
    //注意二分的范围： 
	//金币数越大，显然更容易满足条件。 
	//所以遇到满足条件的就往左边找更小的，不满足的话就找右边找满足的。 
    while(L < R) {
        int mid = L + R >> 1;
        if(check(mid)) {
            ans = mid;
            R = mid;
        }
        else L = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57