柚子快报激活码778899分享：算法 蓝桥杯：蜗牛（Java）
目录
题目描述：输入格式输出格式代码实现：
题目描述：
这天，一只蜗牛来到了二维坐标系的原点。 在α轴上长有n根竹竿。它们平行于y轴，底部纵坐标为0，横坐标分别为a1, a2, …, n。竹竿的高度均为无跟高，宽度可忽略。蜗牛想要从原点走到第n个竹竿的底部也就是坐标(xn,0)。它只能在α轴上或者竹竿上爬行，在α轴上爬行速度为1单位每秒;由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为0.7单位每秒和1.3单位每秒。 为了快速到达目的地，它施展了魔法，在第i和i＋1根竹竿之间建立了传送门(0 x i + 1 x_{i+1} xi+1, b i + 1 b_{i+1} bi+1)，请计算蜗牛最少需要多少秒才能到达目的地。 输入格式 输入共1＋n行，第一行为一个正整数n; 第二行为n个正整数c1, 2, …, n ; 后面n―1行，每行两个正整数ai,bi+1。 3 1 10 11 1 1 2 1 输出格式 输出共一行，一个浮点数表示答案(四舍五入保留两位小数)。 4.20 代码实现： import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner scan = new Scanner(System.in); // 在此输入您的代码... int n = scan.nextInt();// n根竹竿 int[] arr = new int[n];// 存储每个横坐标的值 for (int i = 0; i < arr.length; i++) { arr[i] = scan.nextInt(); } // 记录坐标两两之间的传送点的对应位置 // 共有n-1组数据：0表示传送门1的高度a，1表示传送门2的高度b int[][] transmit = new int[n][2]; for (int i = 0; i < n - 1; i++) { transmit[i][0] = scan.nextInt(); transmit[i][1] = scan.nextInt(); } // dp[i][0]表示到达第i个坐标的最短时间,dp[i][1]表示到达第i个传送们的最短时间 double[][] dp = new double[n + 1][2]; // 计算第一组dp值 dp[1][0] = arr[0];// 横坐标距离 dp[1][1] = arr[0] + transmit[0][0] / 0.7;// 横坐标距离 + 向上爬到传送门距离 int a, b; // 动态规划：打表遍历获得dp的值 for (int i = 2; i <= n; i++) { a = transmit[i - 1][0];// 下一次传送门的高度 b = transmit[i - 2][1];// 当前传送之后的高度 int pos = arr[i - 1] - arr[i - 2];// 距离下一个坐标点的距离 if (a > b) { // 传送之后比下一次传送的位置更低 dp[i][1] = Math.min(dp[i - 1][0] + pos + a / 0.7, dp[i - 1][1] + (a - b) / 0.7); // 计算走传送路径的最短时间：比较两种情况 // 一，上一轮到达坐标点的时间 + 到达下一个坐标点的距离 + 向上爬行到传送门的距离 // 二，上一轮到达传送门的距离 + 向上爬行到下一次传送的距离 } else { // 传送之后比下一次传送的位置更高或者等高 dp[i][1] = Math.min(dp[i - 1][0] + pos + a / 0.7, dp[i - 1][1] + (b - a) / 1.3); // 与上面判断不同的是：第二种情况需要向上爬行到指定传送位置 } // 计算到达坐标轴的时间 dp[i][0] = Math.min(dp[i - 1][1] + b / 1.3, dp[i - 1][0] + pos);// 分为两种情况 // 情况一：刚传送过来可能不在坐标点上，上一轮传送时间 + 向下爬行的时间 // 情况二：刚好在坐标点上，上一轮到达坐标点时间 + 到达下一个坐标点的距离 } System.out.printf("%.2f", dp[n][0]);// 输出最后一轮到达坐标点的时间 scan.close(); } } 柚子快报激活码778899分享：算法 蓝桥杯：蜗牛（Java） 精彩内容
您阅读本篇文章共花了：
发表评论