第十四届蓝桥杯大赛B组 JAVA 蜗牛 (递归剪枝）

题目描述：

这天，一只蜗牛来到了二维坐标系的原点。在 x 轴上长有 n 根竹竿。它们平行于 y 轴，底部纵坐标为 0，横坐标分别为 x1, x2,
…, xn。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 (xn, 0)。它只能在 x
轴上或者竹竿上爬行，在 x 轴上爬行速度为 1 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和
1.3 单位每秒。为了快速到达目的地，它施展了魔法，在第 i 和 i + 1 根竹竿之间建立了传送门（0 < i < n），如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi , ai)，就可以瞬间到达第 i + 1 根竹竿的高度为 bi+1 的位置 (xi+1,
bi+1)，请计算蜗牛最少需要多少秒才能到达目的地。输入格式输入共 1 + n 行，第一行为一个正整数 n；第二行为 n 个正整数
x1, x2, . . . , xn；后面 n − 1 行，每行两个正整数 ai , bi+1。

输出格式：

输出共一行，一个浮点数表示答案（四舍五入保留两位小数）。

样例输入：

3
1 10 11
1 1
2 1

样例输出：

4.20

提示

蜗牛路线：
(0, 0) → (1, 0) → (1, 1) → (10, 1) → (10, 0) → (11, 0)，花费时间为 1+1/0.7+0+1/1.3+1 ≈ 4.20

对于 20% 的数据，保证 n ≤ 15；
对于 100% 的数据，保证 n ≤ 10^5，ai , bi ≤ 10^4，xi ≤ 10^9。

解题思路：

动态规划问题，典型看解析会，自己解就蒙der

分析问题本质，蜗牛由一个杆子到达另一个杆子，要么从本竿的起点出发或本竿的传送点出发，那么问题的核心在于确保到由初始原点到达本竿起点，和到达本竿的传送点必须是最优解

整个示例过程的递归图，以及筛选过程如下：

在这里插入图片描述
a2是第二个竹竿的起点o->a1->a2和o->b1->a2的最终效果一样,都是到达第二个竹竿起点，所以保留时间最少的那个即可，同理保留到b2时间最少的那个即可，这便是筛选剪枝

筛选递推公式：

设 x1 表示从起始位置到当前在竹竿底部所需要的最短时间
设 x2 表示从起始位置到当前到达竹竿传送门起点位置的最短时间
则有
x1 = min(两根竹竿的距离差 + x1, x2 + 上一个门终点高度 / 1.3)
x2 = min(两根竹竿的距离差 + x1 + 当前门起点高度 / 0.7, 上一个门终点到当前门所需要的时间 + x2)
最后的目标是遍历到终点的 x1

剪枝后的效果：
在这里插入图片描述

代码：

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();  // 第一行
         int x[] = new int[n + 1];  // x轴
         for(int i = 1; i <= n; i ++) x[i] = sc.nextInt();
         
         if(n == 1) {  // 只有一个竹竿
        	 System.out.printf("%.2f", (double)x[1]);
        	 return;
         }
         
         int door[][] = new int [n][2];  // 存坐标
         for(int i = 1; i < n; i ++) { 
        	 door[i][0] = sc.nextInt();
        	 door[i][1] = sc.nextInt();
         }
         
         double x1 = x[1], x2 = door[1][0] / 0.7 + x[1];  // 初始化x1,x2
         for(int i = 2; i <= n; i ++) {  // 开始遍历
        	 int d = x[i] - x[i - 1];
        	 double y1 = Math.min(d + x1, x2 + door[i - 1][1] / 1.3);  //先算到达底部
        	 if(i == n) {  // 如果已经是最后一个竹竿
        		 System.out.printf("%.2f", y1);
        		 return;
        	 }
        	 // 要考虑到达的本竹竿的传送点位置和由上一个竹竿传送过来的位置之间关系
        	 x2 = Math.min(d + x1 + door[i][0] / 0.7, x2 + (door[i][0] > door[i - 1][1] ? (door[i][0] - door[i - 1][1]) / 0.7 : (door[i - 1][1] - door[i][0]) / 1.3));
        	 x1 = y1;
         }
    }
}