💎 宝藏

📘 题目描述

在一张大小为 N × M 的地图上，散落着 P 个宝藏。探险者从 (1,1) 出发，每次只能向右或向下走一步。

他希望尽量少的“趟数”把所有宝藏都取完。每次走一趟，探险者从 (1,1) 出发，依次走到目标宝藏并捡起。

你需要计算：至少要走多少趟，才能取完所有宝藏？

📥 输入格式

• 第一行输入三个整数：N, M, P，分别表示地图的行数、列数和宝藏的数量。
• 接下来 P 行，每行两个整数 x, y，表示宝藏的位置（1 ≤ x ≤ N, 1 ≤ y ≤ M）。

📤 输出格式

• 输出一个整数，表示至少需要的趟数。

📌 输入样例

7 7 7
1 2
1 4
2 4
2 6
4 4
4 7
6 6

📌 输出样例

2

🧠 解题思路

由于每次只能“向右”或“向下”，意味着路径只能在坐标平面上从左上向右下“单调递增”。因此，​一次路径所能经过的点，构成一个右下方向的链​。

我们希望在​尽量少的路径中覆盖所有点​，这个问题可以转化为：

将所有宝藏点划分为尽量少的“右下方向单调链”集合。

等价于：

在平面上寻找宝藏点的反向最长上升子序列 LIS（按 x 升序，y 反向 LIS）个数。

操作流程：

1. 对所有宝藏坐标 (x, y) 按 x 升序排列；
2. 对 y 值取一个最长 不下降子序列（LIS） 的个数（因为我们希望最少路径数）；
3. 最终路径数 = 总点数 - LIS长度 + 1

或者​直接求 LIS 长度​，因为我们要求的是：最多能覆盖多少点的一条路径 → 那么最少路径数就是 P - LIS + 1。

但由于方向固定，每次最多覆盖一个“向下右”路径的点链，​最终路径数就是 LIS 的个数​。