路径 - 题解

标签与难度

标签: 动态规划, DP优化, 排序, 扫描线, 前缀和思想, 计算几何难度: 1900

题目大意喵~

你好呀，指挥官！这道题是这样的：

在一个二维平面上，散落着 n 个可爱的点，每个点都有自己的 (x, y) 坐标。我们还有一个由 'L', 'R', 'U', 'D' 组成的指令字符串 s，长度为 m。

我们的任务是，判断是否存在一个由 m+1 个点组成的序列 p_0, p_1, ..., p_m（这些点都必须从给定的 n 个点中选取，但可以重复哦！），这个序列需要满足 m 个移动条件。具体来说，对于每一步 i (从 0 到 m-1)，从点 p_i 移动到点 p_{i+1} 必须严格遵守指令 s[i] 的规则：

L (左): p_{i+1} 必须在 p_i 的正左方，也就是说 x_{p_{i+1}} < x_{p_i} 并且 y_{p_{i+1}} = y_{p_i}。
R (右): p_{i+1} 必须在 p_i 的正右方，x_{p_{i+1}} > x_{p_i} 且 y_{p_{i+1}} = y_{p_i}。
U (上): p_{i+1} 必须在 p_i 的正上方，x_{p_{i+1}} = x_{p_i} 且 y_{p_{i+1}} > y_{p_i}。
D (下): p_{i+1} 必须在 p_i 的正下方，x_{p_{i+1}} = x_{p_i} 且 y_{p_{i+1}} < y_{p_i}。

如果能找到至少一条这样的路径，我们就开心地输出 "YES"，否则就只好遗憾地输出 "NO" 啦，喵~

解题思路分析

这道题要求我们判断一个满足特定条件的“路径”是否存在。当我们看到这种“经过一系列步骤，判断某种状态是否可达”的问题时，我的直觉就会告诉我：这很可能是动态规划 (Dynamic Programming) 的舞台，喵！

1. 朴素的DP想法

首先，我们来定义一下DP的状态。一个很自然的想法是： dp[i][j] 表示：在执行了 i 步移动指令后，路径有没有可能正好结束在第 j 个点上呢？

状态定义: dp[i][j] 是一个布尔值，true 代表可能，false 代表不可能。
路径长度: 我们的路径有 m+1 个点，p_0, p_1, ..., p_m，这对应了 m 步移动。所以 i 的范围是 0 到 m，j 的范围是 0 到 n-1。
基础状态 (Base Case): 当 i=0 时，我们还没有开始移动。路径的第一个点 p_0 可以是任意一个给定的点。所以，dp[0][j] = true 对所有的 j 都成立。
状态转移: 这是最核心的部分！我们怎么计算 dp[i][j] 呢？ dp[i][j] 为 true 的条件是：存在至少一个点 k，它在第 i-1 步是可达的 (dp[i-1][k] == true)，并且从点 k 到点 j 的移动符合第 i-1 个指令 s[i-1]。

用公式来表达就是：

dp[i][j] = \bigvee_{k=0}^{n-1} (dp[i-1][k] \land \text{can\_move}(k, j, s[i-1]))

其中 can_move(k, j, command) 函数判断从点 k 到点 j 是否符合 command 的要求。\bigvee 是逻辑或（OR）的意思。

这个思路很直接，但我们来分析一下它的复杂度。DP表的大小是 (m+1) x n。计算每个 dp[i][j] 都需要遍历 n 个可能的上一步终点 k。所以总的时间复杂度是 $O(m \times n \times n) = O(m \cdot n^2)$ 。题目中 n 和 m 最大可以是 2000，2000 * 2000^2 = 8 \times 10^9，这速度比我的尾巴摇得还慢，肯定会超时的说！必须想办法优化！

2. 优化的DP思路，喵！

我们再仔细看看状态转移的瓶颈：为了确定 dp[i][j]，我们检查了所有的 k。但真的有必要吗？

比如说，当指令是 U (上) 时，从点 k 移动到点 j 的条件是 x_k = x_j 且 y_j > y_k。看呐！这个条件告诉我们，点 k 和点 j 必须在同一条竖直线上！我们根本不需要检查那些 x 坐标和 j 不同的点！

这给了我们一个绝妙的优化思路：把点按坐标分组处理！

预处理:
- 我们创建两个数据结构。一个用来存放所有在同一竖直线上的点，另一个用来存放所有在同一水平线上的点。std::map 就很适合这个任务，喵~
- points_on_vertical[x]：一个列表，包含所有 x 坐标为 x 的点。
- points_on_horizontal[y]：一个列表，包含所有 y 坐标为 y 的点。
- 为了方便处理，我们把每个列表里的点按另一个坐标排序。比如，points_on_vertical[x] 里的点按 y 坐标从小到大排序；points_on_horizontal[y] 里的点按 x 坐标从小到大排序。
优化后的状态转移: 现在，我们来重新审视状态转移的过程。我们依然是按步骤 i 从 1 到 m 来计算 dp[i]。
- 当指令 s[i-1] 是 'U' (上) 时:
  - 我们遍历所有竖直线（即 points_on_vertical 里的每一个 x 坐标分组）。
  - 对于某条竖直线上的点（已经按 y 升序排好），我们从下往上扫描。
  - 我们用一个 bool 变量 prev_possible 来记录，在这条线上，当前点下方是否存在一个在第 i-1 步可达的点。
  - 扫描开始时，prev_possible = false。
  - 对于线上的每个点 p：
    - dp[i][p] 的值就等于 prev_possible。因为要到达 p，必须从它下面的某个点 k 过来，而 prev_possible 正好告诉我们是否存在这样的 k。
    - 然后，我们更新 prev_possible：prev_possible = prev_possible | dp[i-1][p]。这样，点 p 自己也可能成为后续更高点的“上一步”了。
- 当指令 s[i-1] 是 'D' (下) 时:
  - 逻辑类似，但这次我们要从上往下扫描（y 坐标从大到小）。prev_possible 记录的是当前点上方是否存在可达点。
- 当指令 s[i-1] 是 'R' (右) 时:
  - 我们遍历所有水平线，按 x 坐标从小到大扫描。prev_possible 记录的是当前点左方是否存在可达点。
- 当指令 s[i-1] 是 'L' (左) 时:
  - 我们遍历所有水平线，按 x 坐标从大到小扫描。prev_possible 记录的是当前点右方是否存在可达点。

通过这种方式，对于每一步 i，我们只需要遍历所有点一次（按分组后的顺序）。所以每一步的计算复杂度从 $O(n^2)$ 降到了 $O(n)$ ！

3. 最终的方案

预处理: O(n \log n)，主要是排序。
DP计算: m 步，每步 O(n)。总共 O(m \cdot n)。
最终答案: 在计算完所有 dp 表后，我们检查 dp[m] 这一行。只要有任何一个 dp[m][j] 为 true，就说明存在一条合法路径，输出 "YES"。如果 dp[m] 全是 false，就输出 "NO"。

这个 O(n \log n + m \cdot n) 的方案就快多啦，完全可以通过！这种利用问题约束（如坐标关系）来优化DP转移的方法，就像猫咪找到最快的路径抓老鼠一样，高效又优雅，喵~

代码实现

下面是我根据上面的思路，精心重构的一份代码，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

// 为了方便，我们定义一个点的结构体
struct Point {
    int id;
    int x, y;
};

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::string s;
    std::cin >> s;

    std::vector<Point> points(n);
    // 使用 map 来按坐标分组，喵~
    // map 的 key 是 x/y 坐标，value 是这条线上所有点的列表
    // 列表里存 pair<坐标, 点的原始id>，方便排序
    std::map<int, std::vector<std::pair<int, int>>> vertical_lines;
    std::map<int, std::vector<std::pair<int, int>>> horizontal_lines;

    for (int i = 0; i < n; ++i) {
        points[i].id = i;
        std::cin >> points[i].x >> points[i].y;
        vertical_lines[points[i].x].push_back({points[i].y, i});
        horizontal_lines[points[i].y].push_back({points[i].x, i});
    }

    // 对每个分组内的点进行排序
    for (auto& pair : vertical_lines) {
        std::sort(pair.second.begin(), pair.second.end());
    }
    for (auto& pair : horizontal_lines) {
        std::sort(pair.second.begin(), pair.second.end());
    }

    // dp[i][j]: 走 i 步后，是否可能停在点 j
    // 我们用两个 vector 来滚动优化空间，一个存上一步状态，一个存当前步状态
    std::vector<bool> prev_dp(n, true); // 第0步，任何点都可以是起点
    std::vector<bool> curr_dp(n, false);

    for (int i = 0; i < m; ++i) {
        std::fill(curr_dp.begin(), curr_dp.end(), false); // 重置当前步的状态
        char move = s[i];

        if (move == 'U') {
            for (auto const& [x_coord, line_points] : vertical_lines) {
                bool possible_prev = false;
                // 从下往上扫描
                for (auto const& p : line_points) {
                    int point_id = p.second;
                    curr_dp[point_id] = possible_prev;
                    possible_prev |= prev_dp[point_id];
                }
            }
        } else if (move == 'D') {
            for (auto const& [x_coord, line_points] : vertical_lines) {
                bool possible_prev = false;
                // 从上往下扫描
                for (auto it = line_points.rbegin(); it != line_points.rend(); ++it) {
                    int point_id = it->second;
                    curr_dp[point_id] = possible_prev;
                    possible_prev |= prev_dp[point_id];
                }
            }
        } else if (move == 'R') {
            for (auto const& [y_coord, line_points] : horizontal_lines) {
                bool possible_prev = false;
                // 从左往右扫描
                for (auto const& p : line_points) {
                    int point_id = p.second;
                    curr_dp[point_id] = possible_prev;
                    possible_prev |= prev_dp[point_id];
                }
            }
        } else if (move == 'L') {
            for (auto const& [y_coord, line_points] : horizontal_lines) {
                bool possible_prev = false;
                // 从右往左扫描
                for (auto it = line_points.rbegin(); it != line_points.rend(); ++it) {
                    int point_id = it->second;
                    curr_dp[point_id] = possible_prev;
                    possible_prev |= prev_dp[point_id];
                }
            }
        }
        prev_dp = curr_dp; // 滚动到下一步
    }

    bool possible_path = false;
    for (int i = 0; i < n; ++i) {
        if (curr_dp[i]) {
            possible_path = true;
            break;
        }
    }

    if (possible_path) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 加速输入输出，像猫一样敏捷！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot (N \log N + M \cdot N))$
- 对于每组测试数据 T：
- 读取输入和分组点需要 $O(N)$ 。
- 对 map 中的每个 vector 进行排序，所有点合起来总共被排序一次，所以是 $O(N \log N)$ 。
- DP的主循环执行 M 次。在每次循环中，我们遍历所有分组，而每个点恰好属于一个分组，所以内层操作的总和是 $O(N)$ 。因此，DP部分是 $O(M \cdot N)$ 。
- 总和起来就是 $O(N \log N + M \cdot N)$ 啦。
空间复杂度: $O(N + M \cdot N)$ 或 $O(N)$
- 存储 n 个点和分组后的点需要 $O(N)$ 空间。
- DP表如果完整存储是 $O(M \cdot N)$ 。但在我的代码实现中，我使用了滚动数组的技巧（用 prev_dp 和 curr_dp），只保留了上一步和当前步的状态，所以DP部分的空间复杂度降到了 $O(N)$ 。因此，整体空间复杂度是 $O(N)$ ，非常节省内存的说！

知识点总结

这道题真是一次有趣的冒险，让我们来总结一下学到的东西吧，喵~

动态规划 (DP): 它是解决这类多阶段决策问题的基石。准确定义 dp 状态是成功的第一步。
DP状态优化: 从 $O(N^2)$ 到 $O(N)$ 的优化是本题的精髓。关键在于利用题目给出的约束条件（移动必须在同一直线上）来减少不必要的计算。
按坐标分组与排序: 这是计算几何和相关问题中非常常用的技巧。将看似杂乱的点按坐标组织起来，能极大地简化问题结构。
前缀/后缀思想 (扫描线): 在排好序的序列上，用一个变量（possible_prev）来维护“到目前为止”的信息，这本质上是一种前缀和（或后缀和）的思想。在这里，我们求的是“逻辑或”的前缀和。
滚动数组: 当DP状态只依赖于前一（或前几）个状态时，可以使用滚动数组来优化空间复杂度，这在 M 或 N 很大时尤其重要。

希望这篇题解能让你对DP优化有更深的理解！继续加油哦，指挥官，编程的世界就像一个大大的毛线球，充满了探索的乐趣！喵~

路径 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 朴素的DP想法 ​

2. 优化的DP思路，喵！ ​

3. 最终的方案 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​