【线性动态规划】

解题思路:

注意事项:

参考代码:

import java.io.*;
import java.util.Arrays;

/**
 * @Author:杨雨彤
 * @date:2024/1/29 21:51
 */
public class Lq2023蜗牛 {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        int n=Integer.parseInt(br.readLine());
        int []a=new int[n];//记录当前竿子的纵坐标传送门
        int []b=new int[n];//记录瞬移到另一根竿子上的纵坐标
        int []x=new int[n];//记录每根竿子的横坐标
        String[] s = br.readLine().split(" ");
        for (int i = 0; i <x.length ; i++) {
            x[i]=Integer.parseInt(s[i]);
        }
        for (int i = 0; i <n-1 ; i++) {
            String[] s1 = br.readLine().split(" ");
            a[i]=Integer.parseInt(s1[0]);
            b[i]=Integer.parseInt(s1[1]);
        }
        double[][]dp=new double[n][2];   //dp[i][0]表示不用魔法到达第i根竿子底部用时  dp[i][1]表示用魔法到达第i根竿子传送门出发点的用时
        dp[0][0]=x[0];
        dp[0][1]=x[0]+a[0]/0.7;
        for (int i = 1; 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]+(a[i]>b[i-1]?(a[i]-b[i-1])/0.7:(b[i-1]-a[i])/1.3));
        }
        pw.printf("%.2f",dp[n-1][0]);
        pw.flush();
    }
}