题解 3173: 蓝桥杯2023年第十四届省赛真题-蜗牛（动态规划，Java）

解题思路:

动态规划两个数组变量：

// 坐标原点距竹子传送点最短时间
// minStart[i]代表坐标原点距第i个竹子上的传送点的最短时间，i从1开始
double[] minStart = new double[n];
// 坐标原点距竹子底部最短时间
// minBottom[i]代表坐标原点距第i个竹子底部的最短时间，i从1开始
double[] minBottom = new double[n + 1];

根据图可知，到达第i（i>1）根竹子的传送点时，minStart[i]最短时间为：(x_i-1=>x_i=>a_i)或者(x_i-1=>a_i-1=>b_i=>a_i)或者(a_i-1=>b_i=>a_i)，即分别为（5-6-2）或（5-1-2）或（1-2）。

根据图可知，到达第i（i>1）根竹子的底部时，minBottom[i]最短时间为：(x_i-1=>x_i)或者(x_i-1=>a_i-1=>b_i=>x_i)或者(a_i-1=>b_i=>x_i)，即分别为（7-8）或（7-3-4-8）或（3-4-8）。

参考代码:

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); // 多少根竹子
		// 竹子所在的横坐标
		// x[i]代表第i个竹子所在的横坐标，i从1开始
		int[] x = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			x[i] = scanner.nextInt();
		}
		// 竹子的传送点
		// start[i]代表第i个竹子上的传送点纵坐标，i从1开始
		int[] start = new int[n + 1];
		// 竹子传送点的目的点
		// end[i]代表第i-1个竹子传送到第i个竹子的纵坐标，i从1开始
		int[] end = new int[n + 1];
		for (int i = 1; i < n; i++) {
			start[i] = scanner.nextInt();
			end[i + 1] = scanner.nextInt();
		}

		// 坐标原点距竹子传送点最短时间
		// minStart[i]代表坐标原点距第i个竹子上的传送点的最短时间，i从1开始
		double[] minStart = new double[n];
		// 坐标原点距竹子底部最短时间
		// minBottom[i]代表坐标原点距第i个竹子底部的最短时间，i从1开始
		double[] minBottom = new double[n + 1];

		// 初始化minStart[1]与minBottom[1]
		minBottom[1] = x[1]; // 第一根竹子的横坐标即为源点至第1个竹子底部的最短时间
		// 先从源点到达底部，再从底部向上爬到传送点位置，速度为0.7
		if (n > 1) {
			minStart[1] = minBottom[1] + start[1] / 0.7;
		}

		// 动态规划
		for (int i = 2; i <= n; i++) {
			// 根据图可知，到达第i（i>1）根竹子的传送点时，最短时间为：(xi-1=>xi=>ai)
			// 或者(xi-1=>ai-1=>bi=>ai)或者(ai-1=>bi=>ai)
			if (i < n) {
				// 只有前n-1根竹子有传送点
				minStart[i] = getMin(new double[] { minBottom[i - 1] + (x[i] - x[i - 1]) + getTimeByHeight(0, start[i]),
						minBottom[i - 1] + getTimeByHeight(0, start[i - 1]) + 0 + getTimeByHeight(end[i], start[i]),
						minStart[i - 1] + 0 + getTimeByHeight(end[i], start[i]) });
			}
			// 根据图可知，到达第i（i>1）根竹子的底部时，最短时间为：(xi-1=>xi)
			// 或者(xi-1=>ai-1=>bi=>xi)或者(ai-1=>bi=>xi)

			minBottom[i] = getMin(new double[] { minBottom[i - 1] + x[i] - x[i - 1],
					minBottom[i - 1] + getTimeByHeight(0, start[i - 1]) + 0 + getTimeByHeight(end[i], 0),
					minStart[i - 1] + 0 + getTimeByHeight(end[i], 0) });

		}

		// minBottom[n]即为最优解
		System.out.printf("%.2f", minBottom[n]);
	}

	/*
	 * 返回数组中的最小值
	 */
	public static double getMin(double[] args) {
		if (args.length <= 0) {
			return -1;
		}
		double min = args[0];
		for (int i = 1; i < args.length; i++) {
			min = min > args[i] ? args[i] : min;
		}

		return min;
	}

	/*
	 * 根据高度，返回爬行时间
	 */
	public static double getTimeByHeight(int start, int end) {
		double speed = start > end ? 1.3 : -0.7;
		return (start - end) / speed;
	}
}