洛谷 P3957 跳房子 题解

发表于 | 分类于 | | 热度: ℃

Description

跳房子的游戏规则如下：在地面上有一个起点，起点右侧有 $n$ 个格子，在同一直线上。每个格子内有一个整数，表示到达该格子能得到的分数。规则规定：玩家每次都必须跳到当前位置右侧的一个格子内，可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

小 $R$ 研发了一款弹跳机器人参加游戏。机器人有一个缺陷，它每次向右弹跳的距离只能为固定的 $d$ 。如果小 $R$ 花 $g$ 个金币改进他的机器人，机器人的灵活性就增加 $g$，但是每次弹跳的距离至少为 $1$。具体而言，当 $g<d$ 时，他的机器人每次可以选择向右弹跳的距离为 $d-g$ , $d-g+1$ , $d-g+2$ , $…$ , $d+g-2$ , $d+g-1$ , $d+g$；否则，他的机器人每次可以选择向右弹跳的距离为 $1$ , $2$ , $3$ , … , $d+g-2$ , $d+g-1$ , $d+g$。

小 $R$ 希望获得至少 $k$ 分，问他至少要花多少金币改造机器人。

数据范围：$1≤n≤500000 , 1≤d≤2000 , 1≤x_i , k≤10^9 , |s_i|<10^5$

做法1

二分答案。用 $dp$ 来判断当前答案是否可行。$f[i]$ 表示跳到第 $i$ 个格子的最大得分。如果 $f[0-n]$ 中有任意一个 $>=k$，当前答案可行。否则不可行。

另外注意，二分的右边界要取 $d$ 与第 $n$ 个格子到原点距离的最大值。

复杂度为 $O(n^2)$，可以得到 $50$ 分。

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;

const int N = 1000000;
int n, d, k, l, r, ans = 0x3f3f3f3f, x[N], s[N], f[N];

inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    return f * x;
}

int max_(int x, int y) { return x > y ? x : y; }

bool get(int g)
{
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for(int i = 0; i <= n; i++)
    {
        int a = x[i] + max_(1, d - g), b = x[i] + d + g;
        for(int j = i + 1; j <= n; j++)
            if(x[j] >= a && x[j] <= b)
                f[j] = max_(f[j], f[i] + s[j]);
    }
    for(int i = 0; i <= n; i++)
        if(f[i] >= k) return true;
    return false;
}

signed main()
{
    n = read(), d = read(), k = read();
    for(int i = 1; i <= n; i++)
        x[i] = read(), s[i] = read();
    l = 0, r = max_(d, x[n] + 1);
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(get(mid))
        {
            if(ans > mid) ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    printf("%lld", ans);
    return 0;
}

单调队列优化

可以发现格子每次向后移动，答案区间也跟着向后滑动。区间的两端点单调递增。

对 $dp$ 验证过程加一个单调队列优化。$q$ 存的是编号，$next$ 是当前轮到哪一个点入队。$i$ 每加一次就使 $next$ 以及后面进入区间的都入队，使前面不再区间内的出队。如果队列非空：
f[i] = f[q[head]] + s[i]

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;

const int N = 1000000;
int n, d, k, l, r, head, tail, next, ans = 0x3f3f3f3f;
int q[N], p[N], x[N], s[N], f[N];

inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    return f * x;
}

int max_(int x, int y) { return x > y ? x : y; }

bool get(int g)
{
    memset(f, -0x3f, sizeof(f));
    int head = 1, tail = 0, next = 0, ma = d + g, mi = d - g;
    mi = max_(mi, 1);
    f[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        while(x[next] + mi <= x[i])
        {
            while(head <= tail && f[q[tail]] <= f[next])
                tail--;
            q[++tail] = next;
            next++;
        }
        while(head <= tail && x[q[head]] + ma < x[i])
            head++;
        if(head <= tail) f[i] = f[q[head]] + s[i];
        if(f[i] >= k) return true;
    }
    return false;
}

signed main()
{
    n = read(), d = read(), k = read();
    for(int i = 1; i <= n; i++)
        x[i] = read(), s[i] = read();
    x[0] = s[0] = 0;
    l = 0, r = max_(d, x[n] + 1);
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(get(mid))
        {
            if(ans > mid) ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    if(ans != 0x3f3f3f3f) printf("%lld", ans);
    else printf("-1");
    return 0;
}