自动搬运

查看原文

来自洛谷，原作者为

	helium347 patience...

搬运于2025-08-24 22:34:27，当前版本为作者最后更新于2022-03-07 14:28:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

线性dp && 维护前缀和

题意

• 告诉你 $n$ 个点的点权、坐标。
• 你可以从 $(x,y)$ 移动到 $(x + i, y)$ 或 $(x, y + i)$ , $i$ > 0。
• 每次移动到另一个点需要消耗 $k$ 点能量。
• 移动后可以补充该点点权的能量。

求从点 $1$ 到点 $n$ 的一条路径，并打印路径。

思路

1. 线性dp

   • 无后效性：每次移动，横纵坐标只会变大或不变。
   • 最优子结构： 显然。

2. 前缀和

   • $n < 10 ^ 5$，所以 $n^2$ 枚举超时。

3. 排序

   • 保证dp顺序。
   • 维护前缀和。

实现

• $f[i]$ : 移动到节点 $i$ 的最大剩余能量。
• $pre[i]$ : 最优解的情况下，节点 $i$ 的前驱。
• $prex[i]$ : 当前状态下，第 $i$ 行的前缀中，使 $f[i]$ 最大的下标。
• $prey[i]$ : 当前状态下，第 $i$ 列的前缀中，使 $f[i]$ 最大的下标。

于是有：

$f[i] = max(f[j] - cost + w[i])$

代码

// https://www.luogu.com.cn/problem/P7936
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
int rad(); // read int
const int max_size = 5 + 1e5;
const int maxn = 5 + 3e5;

int n, cost;
struct Pos {
    int x, y, w, id;
    bool operator<(const Pos &other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
} pos[maxn];

int pre[maxn];              // pre[i]: 到达 node i  的最优解的前一步
int f[maxn];                // 到达节点 i 所剩能量的最大值
int prex[maxn], prey[maxn]; //
// f[i] = max(f[j] - cost + w[i]), j to i

void show(int now, int dep = 0) {
    if (now == 0) {
        printf("%d\n", dep);
        return;
    };
    show(pre[now], dep + 1);
    printf("%d %d\n", pos[now].x, pos[now].y);
}

void update(int now, int from) {
    if (from == 0 || f[from] < cost) return;
    if (f[now] < f[from] - cost + pos[now].w) {
        f[now] = f[from] - cost + pos[now].w;
        pre[now] = from;
    }
}

int main() {
    n = rad(), cost = rad();
    rf(i, n) {
        pos[i].x = rad(), pos[i].y = rad(), pos[i].w = rad();
        pos[i].id = i;
    }
    sort(pos + 1, pos + 1 + n);
    int start = 1, finish = 1; // 找到起点，终点
    while (pos[start].id != 1)
        start++;
    while (pos[finish].id != n)
        finish++;

    f[start] = pos[start].w, prex[pos[start].x] = start, prey[pos[start].y] = start;
    for (int i = start + 1; i <= finish; ++i) {
        update(i, prex[pos[i].x]);
        update(i, prey[pos[i].y]);
        if (f[i] > f[prex[pos[i].x]]) prex[pos[i].x] = i;
        if (f[i] > f[prey[pos[i].y]]) prey[pos[i].y] = i;
    }
    printf("%d\n", f[finish]);
    show(finish);
}

int rad() {
    int back = 0, ch = 0, neg = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        neg = ch == '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return (back ^ -neg) + neg;
}