网站服务器 数据库服务器深圳新闻今日最新

题目链接

这道题我感觉状态定义不太好想，需要一定的经验

import java.util.*;
/*** 蜗牛* 状态定义：* dp[i][0]:到达(x[i],0)最小时间* dp[i][1]:到达 xi 上方的传送门最小时间*/public class Main {static Scanner in = new Scanner(System.in);static final int N = 100010,INF = 0x3f3f3f3f;static int n;static int[] x = new int[N];static double[][] dp = new double[N][2];static int[] a,b;public static void main(String[] args) {n = in.nextInt();a = new int[n+1];b = new int[n+1];for (int i = 1;i <= n;i++) {x[i] = in.nextInt();}for (int i = 1;i <= n-1;i++) {a[i] = in.nextInt();b[i] = in.nextInt();}for (int i = 2;i <= n;i++) {dp[i][0] = dp[i][1] = INF;}dp[1][0] = x[1];dp[1][1] = x[1] + a[1]/0.7;for (int i = 2;i <= n;i++) {// 到达i底部有两种办法// 1.从i-1底部爬过来// 2.从i-1的传送门过来，然后再爬下来dp[i][0] = Math.min(dp[i-1][0] + x[i] - x[i-1],dp[i-1][1] + b[i-1]/1.3);// 到达i上方传送门有两种办法// 1.从i-1的传送门过来，然后向上or向下爬// 2.从i底部爬上来double time = 0.0; // 从i-1传送过来的位置爬到i的传送门的时间if (b[i-1] < a[i]) time = (a[i] - b[i-1])/0.7;else time = (b[i-1] - a[i])/1.3;dp[i][1] = Math.min(dp[i][0] + a[i]/0.7,dp[i-1][1] + time);}System.out.printf("%.2f",dp[n][0]);}
}