Skip to content

「NOIP2017」跳房子

题解约 2.1 千字
# 洛谷 # 动态规划 # 单调队列 # 单调队列优化 DP # 2017 # NOIP
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下：

在地面上确定一个起点，然后在起点右侧画 nn 个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个 格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 dd。小 R 希望改进他的机器人，如果他花 gg 个金币改进他的机器人，那么他的机器人灵活性就能增加 gg，但是需要注意的是，每 次弹跳的距离至少为 11。具体而言，当 g<dg < d 时，他的机器人每次可以选择向右弹跳的距离为 d−g,d−g+1,d−g+2,…,d+g−1,d+gd - g, d - g + 1, d - g + 2, \ldots, d + g - 1, d + g；否则当 g≥dg \geq d 时，他的机器人每次可以选择向右弹跳的距离为 1,2,3,…,d+g−1,d+g1, 2, 3, \ldots, d + g - 1, d + g。

现在小 R 希望获得至少 kk 分，请问他至少要花多少金币来改造他的机器人。

#输入格式

第一行三个正整数 n,d,kn, d, k ，分别表示格子的数目，改进前机器人弹跳的固定距离，以及希望至少获得的分数。相邻两个数 之间用一个空格隔开。

接下来 nn 行，每行两个整数 xi,six_i, s_i ，分别表示起点到第 ii 个格子的距离以及第 ii 个格子的分数。两个数之间用一个空格隔开。保证 xix_i 按递增顺序输入。

#输出格式

共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 kk 分，输出 −1-1。

#输入输出样例

样例输入 #1

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

样例输出 #1

2

样例解释 #1

花费 22 个金币改进后，小 R 的机器人依次选择的向右弹跳的距离分别为 2,3,5,3,4,32, 3, 5, 3, 4, 3，先后到达的位置分别为 2,5,10,13,17,202, 5, 10, 13, 17, 20，对应 1,2,3,5,6,71, 2, 3, 5, 6, 7 这 66 个格子。这些格子中的数字之和 1515 即为小 R 获得的分数。

样例输入 #2

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

样例输出 #2

-1

样例解释 #2

由于样例中 77 个格子组合的最大可能数字之和只有 1818，所以无论如何都无法获得 2020 分。

#数据范围与约定

本题共 10 组测试数据，每组数据等分。

对于全部的数据满足 1≤n≤5×1051 \le n \le 5 \times 10^5，1≤d≤2×1031 \le d \le 2 \times 10^3，1≤xi,k≤1091 \le x_i, k \le 10^9，∣si∣<105|s_i| < 10^5。

  • 对于第 1,21, 2 组测试数据，保证 n≤10n\le 10；
  • 对于第 3,4,53, 4, 5 组测试数据，保证 n≤500n \le 500；
  • 对于第 6,7,86, 7, 8 组测试数据，保证 d=1d = 1。

#思路

显然 gg 的取值可以通过二分的方法得出，因为当花费 gg 枚金币可以得到至少 kk 分时，花费 g+1g + 1 枚也可以得到至少 kk 分。

设 fif_i 表示跳到第 ii 格时获得的最大分数，显然可以朴素地进行转移：

C++
1
2
3
4
5
6
for (int j = 0; j < i; j++) {
    // 如果能从点 j 跳跃到点 i 就更新 f[i]
    if (l <= x[i] - x[j] && x[i] - x[j] <= r) {
        f[i] = std::max(f[i], f[j] + s[i]);
    }
}

这样的时间复杂度为 O(n2log⁡n)O(n^2 \log n)，只能拿到 5050 分。

由于题目中保证了 xix_i 按递增顺序输入，那么在第二重循环时倒序枚举，如果遇到第一个无法从点 jj 跳跃到点 ii 的点，那么直接跳出循环即可。

C++
1
2
3
4
5
6
7
for (int j = i - 1; j >= 0; j--) {
    if (l <= x[i] - x[j] && x[i] - x[j] <= r) {
        f[i] = std::max(f[i], f[j] + s[i]);
    } else if (x[i] - x[j] > r) {
        break;
    }
}

这样就可以拿到 8080 分了。

继续往下想，当 gg 为定值时，随着 ii 的增加，break 时的 jj 的值只会越来越大而不会变小，因此可以用单调队列来维护，就能通过所有的测试点了。

#代码

C++
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
58
59
#include <iostream>
#include <algorithm>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, d;
long long k, f[N], sum;
std::pair<long long, long long> a[N];

bool check(long long l, long long r) {
    for (int i = 1; i <= n; i++) {
        f[i] = -INF;

        for (int j = 0; j < i; j++) {
            if (l <= a[i].first - a[j].first && a[i].first - a[j].first <= r) {
                f[i] = std::max(f[i], f[j] + a[i].second);
            }
        }

        if (f[i] >= k) return true;
    }

    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d >> k;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;

        sum += a[i].second;
    }

    long long l = 0, r = INF;

    while (l < r) {
        long long mid = l + r >> 1;

        if (check(std::max(d - mid, 0ll), d + mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << (r == INF ? -1 : r) << endl;

    return 0;
}
C++
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
58
59
60
61
#include <iostream>
#include <algorithm>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, d;
long long k, f[N], sum;
std::pair<long long, long long> a[N];

bool check(long long l, long long r) {
    for (int i = 1; i <= n; i++) {
        f[i] = -INF;

        for (int j = i - 1; ~j; j--) {
            if (l <= a[i].first - a[j].first && a[i].first - a[j].first <= r) {
                f[i] = std::max(f[i], f[j] + a[i].second);
            } else if (a[i].first - a[j].first > r) {
                break;
            }
        }

        if (f[i] >= k) return true;
    }

    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d >> k;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;

        sum += a[i].second;
    }

    long long l = 0, r = INF;

    while (l < r) {
        long long mid = l + r >> 1;

        if (check(std::max(d - mid, 0ll), d + mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << (r == INF ? -1 : r) << endl;

    return 0;
}
C++
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
#include <deque>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5e5 + 5;
const long long INF = 0x3f3f3f3f3f3f3f3f;

int n, d;
long long k, f[N], sum;
std::pair<long long, long long> a[N];

bool check(long long l, long long r) {
    std::deque<long long> q;

    for (int i = 1, j = 0; i <= n; i++) {
        f[i] = -INF;

        while (j < i && l <= a[i].first - a[j].first) {
            if (f[j] != -INF) {
                while (!q.empty() && f[q.back()] <= f[j]) q.pop_back();
                q.push_back(j);
            }

            j++;
        }

        while (!q.empty() && a[i].first - a[q.front()].first > r) {
            q.pop_front();
        }

        if (!q.empty()) {
            f[i] = std::max(f[i], f[q.front()] + a[i].second);
        }

        if (f[i] >= k) return true;
    }

    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d >> k;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;

        sum += a[i].second;
    }

    long long l = 0, r = INF;

    while (l < r) {
        long long mid = l + r >> 1;

        if (check(std::max(d - mid, 0ll), d + mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << (r == INF ? -1 : r) << endl;

    return 0;
}