网站推广的企业,湖南网站建设工作室,网络组建实训报告,化妆品网站建设经济可行性分析题目描述#xff1a; 这天#xff0c;一只蜗牛来到了二维坐标系的原点。 在 x 轴上长有 n 根竹竿。它们平行于 y 轴#xff0c;底部纵坐标为 0#xff0c;横坐标分别为 x1, x2, …, xn。竹竿的高度均为无限高#xff0c;宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也…题目描述 这天一只蜗牛来到了二维坐标系的原点。 在 x 轴上长有 n 根竹竿。它们平行于 y 轴底部纵坐标为 0横坐标分别为 x1, x2, …, xn。竹竿的高度均为无限高宽度可忽略。蜗牛想要从原点走到第 n 个竹竿的底部也就是坐标 (xn, 0)。它只能在 x 轴上或者竹竿上爬行在 x 轴上爬行速度为 1 单位每秒由于受到引力影响蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和 1.3 单位每秒。 为了快速到达目的地它施展了魔法在第 i 和 i 1 根竹竿之间建立了传送门0 i n如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi , ai)就可以瞬间到达第 i 1 根竹竿的高度为 bi1 的位置 (xi1, bi1)请计算蜗牛最少需要多少秒才能到达目的地。 输入格式 输入共 1 n 行第一行为一个正整数 n 第二行为 n 个正整数 x1, x2, . . . , xn 后面 n − 1 行每行两个正整数 ai , bi1。 输出格式 输出共一行一个浮点数表示答案四舍五入保留两位小数。 样例输入 3 1 10 11 1 1 2 1 样例输出 4.20 提示
蜗牛路线 (0, 0) → (1, 0) → (1, 1) → (10, 1) → (10, 0) → (11, 0)花费时间为 11/0.701/1.31 ≈ 4.20
对于 20% 的数据保证 n ≤ 15 对于 100% 的数据保证 n ≤ 10^5ai , bi ≤ 10^4xi ≤ 10^9。
解题思路 动态规划问题典型看解析会自己解就蒙der
分析问题本质蜗牛由一个杆子到达另一个杆子要么从本竿的起点出发或本竿的传送点出发那么问题的核心在于确保到由初始原点到达本竿起点和到达本竿的传送点必须是最优解
整个示例过程的递归图以及筛选过程如下 a2是第二个竹竿的起点o-a1-a2和o-b1-a2的最终效果一样,都是到达第二个竹竿起点所以保留时间最少的那个即可同理保留到b2时间最少的那个即可这便是筛选剪枝
筛选递推公式
设 x1 表示从起始位置到当前在竹竿底部所需要的最短时间 设 x2 表示从起始位置到当前到达竹竿传送门起点位置的最短时间 则有 x1 min(两根竹竿的距离差 x1, x2 上一个门终点高度 / 1.3) x2 min(两根竹竿的距离差 x1 当前门起点高度 / 0.7, 上一个门终点到当前门所需要的时间 x2) 最后的目标是遍历到终点的 x1
剪枝后的效果
代码
import java.util.Scanner;
public class Main {public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt(); // 第一行int x[] new int[n 1]; // x轴for(int i 1; i n; i ) x[i] sc.nextInt();if(n 1) { // 只有一个竹竿System.out.printf(%.2f, (double)x[1]);return;}int door[][] new int [n][2]; // 存坐标for(int i 1; i n; i ) { door[i][0] sc.nextInt();door[i][1] sc.nextInt();}double x1 x[1], x2 door[1][0] / 0.7 x[1]; // 初始化x1,x2for(int i 2; i n; i ) { // 开始遍历int d x[i] - x[i - 1];double y1 Math.min(d x1, x2 door[i - 1][1] / 1.3); //先算到达底部if(i n) { // 如果已经是最后一个竹竿System.out.printf(%.2f, y1);return;}// 要考虑到达的本竹竿的传送点位置和由上一个竹竿传送过来的位置之间关系x2 Math.min(d x1 door[i][0] / 0.7, x2 (door[i][0] door[i - 1][1] ? (door[i][0] - door[i - 1][1]) / 0.7 : (door[i - 1][1] - door[i][0]) / 1.3));x1 y1;}}
}
