yanciel


私信TA

用户名:dotcpp0709145

访问量:1302

签 名:

等  级
排  名 16407
经  验 771
参赛次数 0
文章发表 6
年  龄 0
在职情况 教师
学  校 郑州工业应用技术学院
专  业

  自我简介:

解题思路:

蜗牛爬行图解.bmp

动态规划两个数组变量:

// 坐标原点距竹子传送点最短时间
// 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]最短时间为:(xi-1=>xi=>ai)或者(xi-1=>ai-1=>bi=>ai)或者(ai-1=>bi=>ai),即分别为(5-6-2)或(5-1-2)或(1-2)。

根据图可知,到达第i(i>1)根竹子的底部时,minBottom[i]最短时间为:(xi-1=>xi)或者(xi-1=>ai-1=>bi=>xi)或者(ai-1=>bi=>xi),即分别为(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;
	}
}


 

0.0分

17 人评分

  评论区