1.3　宝藏

【题目描述】 宝藏（treasure_map）ZJU 2283

一张 N×M的地图上有P个宝藏，探险者每次可以向右或者向下走一步，求最少要走多少步才能找到所有的宝藏。

【输入格式】

第一行有3个整数，分别为N、M和P（1≤N，M≤10 000 000 000，P≤100 000）。余下P行分别为每个宝藏的横、纵坐标。

【输出格式】

一个整数，即次数。

【输入样例】

7 7 7

1 2

1 4

2 4

2 6

4 4

4 7

6 6

【输出样例】

2

【算法分析】

从最简单的地图考虑，如果探险者每次只能向右或者向下走，那么可以发现无论如何都必须要走两步才能走完图1.3所示的两个点。

图1.3

由此可以推断出，如果有K个点连成这样从右上向左下的链，那么取完这K个点至少需要K次。

而其余的点，只要不属于该链，就肯定可以在某一次取值时被取走。

所以，该问题可转化为求最长不下降子序列的问题。