題目描述：
這天，一只蝸牛來到了二維坐標系的原點。 在 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,x2for(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;}}
}
