#P1925. Spiderman

Spiderman

题目描述 章鱼博士绑架了蜘蛛侠的女友 MJ,并将她关在西塔。现在,英雄蜘蛛侠必须尽快到达西塔营救她。他需要使用自己的武器 —— 蛛网 —— 完成这一任务。

从蜘蛛侠的公寓(起点)到西塔之间有一条笔直的道路。道路两旁矗立着许多高楼,这些高楼的高度均大于或等于公寓的高度。蜘蛛侠可以向自己与西塔之间的任意建筑物(包括西塔)顶部发射蛛网,然后荡到该建筑物的另一侧。当他完成一次荡摆时,可以再次向另一建筑物发射蛛网,重复这一过程直到到达西塔。图 1 展示了蜘蛛侠从公寓顶部出发到达西塔的过程:他从 A 荡到 B,再从 B 荡到 C,最后从 C 荡到西塔,共使用 33 次荡摆,这是最优解。

关键规则:

所有建筑物(包括公寓和西塔)均视为直线,且横坐标(Xi)严格递增。 荡摆时,蛛网长度不能超过建筑物高度(即荡摆的水平距离不能超过建筑物高度)。 荡摆方向只能从左到右(不能后退)。 输入 第一行包含测试用例数 K1K20K(1 ≤ K ≤ 20)。 每个测试用例以整数 N2N5000N(2 ≤ N ≤ 5000)开头,表示建筑物数量(包括公寓和西塔)。 接下来N N 行,每行包含两个整数 Xi,YiXi, Yi,表示建筑物的横坐标和高度。第一个建筑物是公寓,最后一个是西塔,且所有建筑物按 XiXi 升序排列,XiXi 互不相同。 输出 对每个测试用例,输出到达西塔所需的最少荡摆次数;若无法到达,输出 - 1。 输入输出示例 输入数据 1:

plaintext 2
6
0 3
3 5
4 3
5 5
7 4
10 4
3
0 3
3 4
10 4

输出数据 1:

plaintext 3
2

解释:

第一个测试用例中,蜘蛛侠的荡摆路径为:公寓(0,3)→ (3,5) → (5,5) → 西塔(10,4),共 3 次。 第二个测试用例中,路径为:公寓(0,3)→ (3,4) → 西塔(10,4),共 2 次。