有 $m+1$ 个星球，从 $0$ 到 $m$ 编号，yqy最初在 $0$ 号星球
有 $n$ 处矿体，第 $i$ 出矿体有 $a_i$ 单位原矿，在编号为 $b_i$ 的星球上
飞船每次只能从 $x$ 号星球移动到 $x+4$ 或 $x+7$ 号星球，每到一个星球yqy会采走该星球上所有的原矿
求yqy最多能采走多少原矿
注意：
- yqy不必最终到达 $m$ 号星球
- 对于 $100\%$ 的数据， $n\leq 10^5, m\leq 10^9$

题解

设 $f(i)$ 表示走到第 $i$ 个星球时最多可以得到的原矿数量，用 $v_i$ 表示第 $i$ 个星球上有的原矿数量，易得：

f(i)=\max(f(i-4),f(i-7))+w_i

然而对于 $100\%$ 的数据， $m$ 很大，这样会超时超内存，所以我们需要做一些优化。

首先扯一会Exgcd：对于一个方程 $ax+by=c$ ，此方程有整数解的充要条件是 $\gcd(a,b)\mid c$ ，对于本题中每一个想要到达的距离 $d$ ，可以写成 $4x+7y=d$ 的形式，由于 $\gcd(4,7)=1$ 所以 $d$ 为任意正整数时，该方程都有整数解。

然而，本题只有当所求 $x,y$ 都为正整数时，才称对应 $d$ 为可到达的。

经过枚举，我们发现，当 $d\geq 18$ 时，对应的 $x,y$ 都为整数，也就是说，如果某两个有矿物的星球之间距离大于等于 $18$ ，我们可以将它们之间的距离压缩成 $18$ ，这样的时间复杂度和空间复杂度就达到了 $O(n\times 18)$ ，极限数据 $n=10^5$ ，轻松过

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
const int MAXN = 1e5;
const int MAXM = 1e9;
struct Mine {
    int pos, val;
    bool operator<(const Mine &other) const { return pos < other.pos; }
} a[MAXN];
int main () {
    freopen("mining.in", "r", stdin);
    freopen("mining.out", "w", stdout);
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a[i].val, &a[i].pos);
    }
    sort(a, a + n);
    int Del = 0, Last = 0, maxPos = 0;
    for (int i = 0; i < n; i++) {//压缩距离
        a[i].pos -= Del;
        int Gap = a[i].pos - Last;
        if (Gap > 18) {
            int t = Gap - 18;
            a[i].pos -= t;
            Del += t;
        }
        Last = a[i].pos;
        maxPos = max(maxPos, a[i].pos);
    }
    static int w[MAXN * 18 + 1], f[MAXN * 18 + 1];
    for (int i = 0; i < n; i++) w[a[i].pos] += a[i].val;
    for (int i = 1; i <= maxPos; i++) f[i] = INT_MIN;
    w[0] = f[0] = 0; int ans = INT_MIN;
    for (int i = 1; i <= maxPos; i++) {
        if (i >= 4) f[i] = max(f[i], f[i - 4] + w[i]);
        if (i >= 7) f[i] = max(f[i], f[i - 7] + w[i]);
        ans = max(ans, f[i]);
    }
    printf("%d\n", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

挖矿，DP，扩展欧几里德

Contents

题解

代码