解题思路:
动态规划两个数组变量:
// 坐标原点距竹子传送点最短时间
// 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 人评分
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:756 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:2081 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:523 |
Minesweeper (C语言描述,蓝桥杯)浏览:1126 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:1173 |
1118(求助_已解决)浏览:329 |
众数问题 (C语言代码)浏览:673 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:514 |
简单的a+b (C语言代码)浏览:561 |
用getchar()函数接收字符,正序输入为什么会倒序输出浏览:741 |