蓝桥杯2023年第十四届省赛真题-蜗牛（用动态规划dp来解）

解题思路:
    因为本题是基于选择最短路径问题，我们可以用动态规划来解决。

    定义dp[i][j] 表示蜗牛走到第 i 根杆子的最短用时，j 表示状态。
    j = 0 : 走到杆子底部
    j = 1 ：走到杆子的传送门处

注意事项:

    在输入时可以为了方便进行从数组1开始输入，简化了写代码的时间。特别注意两个dp数组之间的关系不能出错。

参考代码:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

    //dp[i][0]：走到第i根杆子底部的最短用时

    //dp[i][1]：走到第i根杆子传送带的最短用时

    //状态转移方程：

    //dp[i][0] = dp[i-1][0] + a[i] - a[i - 1] 从上一个状态底部走过来

    //dp[i][0] = dp[i-1][1] + b[i - 1] / 1.3 从当前杆子上爬下来， b[i - 1] 是当前杆子的传送带终点

    //dp[i][1] = dp[i][0] + a[i] / 0.7 从当前杆子底部向上爬

    //dp[i][1] = dp[i-1][1]  从上一个传送带的起点传送过来，这里需要分类讨论，上一个传送带的终点可能和

    //当前杆子的传送带起点不一样

    //如果b[i - 1] > a[i]

    //dp[i][1] = dp[i - 1][1] + (b[i - 1] - a[i]) / 1.3 终点在起点的上面，需要向下爬

    //如果b[i - 1] <= a[i]

    //dp[i][1] = dp[i - 1][1] + (a[i] - b[i - 1]) / 0.7 终点不高于起点，需要向上爬

   //由定义出发，答案就是 f[n][0]

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int [] x = new int[n+1];

        for(int i=1;i<=n;i++){

          x[i] = sc.nextInt();

        }

        int [] a = new int[n+1];

        int [] b = new int[n+1];

        for(int i=1;i<n;i++){

          a[i] = sc.nextInt();

          b[i] = sc.nextInt();

        }

        double [][] dp = new double[n+1][2];

        dp[1][0] = x[1];

        dp[1][1] = x[1]+a[1]/0.7;

        for(int i=2;i<=n;i++){

          dp[i][0] = Math.min(dp[i-1][0]+x[i]-x[i-1],dp[i-1][1]+b[i-1]/1.3);

          dp[i][1] = Math.min(dp[i][0]+a[i]/0.7,dp[i-1][1]+(b[i-1]>a[i]?(b[i-1]-a[i])/1.3:(a[i]-b[i-1])/0.7));

        }

        System.out.printf("%.2f",dp[n][0]);

    }

}