ABC369F F - Gather Coins 题解

题目链接：https://atcoder.jp/contests/abc369/tasks/abc369_f

题目大意：

在一个 \(H \times W\) 的二维迷宫中有 \(N\) 枚硬币，其中第 \(i\) 枚硬币在 \((R_i, C_i)\)（本题中，我们用 \((r, c)\) 表示二维迷宫中从上到下第 \(r\) 行从左到右第 \(c\) 列的那个格子）。

你一开始在迷宫的左上角 \((1, 1)\) 处，你要移动到一共的右下角 \((H, W)\)，但是你每次移动智能向右或向下移动一格。

求：路径上最多能够收集到的硬币数？同时，还要求输出任意一种满足条件的移动方案。

数据范围：

• \(2 \le H, W \le 2 \times 10^5\)
• \(1 \le N \le min(HW-2, 2 \times 10^5)\)
• \((R_i, C_i)\) 各不相同

题解

将所有有硬币的位置 \((r, c)\) 按升序排序。

这里我们定义 \((r_i, c_i) \lt (r_j, c_j)\) 当且仅当 \(r_i \lt r_j\) 或者 \(r_i = r_j\) 的情况下 \(c_i \lt c_j\) 。

我们假设最终移动的过程中依次手机到的硬币的位置构成的序列为：\((r'_1, c'_1)\)，\((r'_2, c'_2)\)，……，\((r'_k, c'_k)\)。

很明显 \(c'_1 \le c'_2 \le \ldots \le c'_k\)。

所以答案就是对 \((r_i, c_i)\) 排序之后对 \(c_i\) 求 LIS（这里是最长飞将子序列），求 LIS 的同时记录一下路径即可。

示例程序：

https://atcoder.jp/contests/abc369/submissions/57359342

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int H, W, n, f[maxn], m, pos[maxn], pre[maxn], ans;
struct Node {
    int r, c;

    bool operator < (const Node &b) const {
        return r < b.r || r == b.r && c < b.c;
    }
} a[maxn];

int main() {
    scanf("%d%d%d", &H, &W, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].r, &a[i].c);
    sort(a+1, a+n+1);
    for (int i = 1; i <= n; i++) {
        int p = upper_bound(f, f+m, a[i].c) - f;
        if (p == m) m++;
        f[p] = a[i].c;
        pos[p] = i;
        if (p)
            pre[i] = pos[p-1];
    }
    printf("%d\n", m);
    vector<Node> vec;
    vec.push_back({H, W});
    for (int i = pos[m-1]; i; i = pre[i])
        vec.push_back({a[i].r, a[i].c});
    vec.push_back({1, 1});
    assert(vec.size() == m+2);
    reverse(vec.begin(), vec.end());
    for (int i = 0; i+1 < m+2; i++) {
        int cnt_d = vec[i+1].r - vec[i].r, cnt_r = vec[i+1].c - vec[i].c;
        while (cnt_d--) putchar('D');
        while (cnt_r--) putchar('R');
    }
    return 0;
}

参考资料：https://atcoder.jp/contests/abc369/editorial/10849