网站新闻不收录,类似于 wordpress,青海省公路建设市场信用信息服务网站,app开发公司定制小程序问题描述 输入格式 输出格式
输出共一行#xff0c;一个浮点数表示答案#xff08;四舍五入保留两位小数#xff09;。
样例输入
3
1 10 11
1 1
2 1样例输出
4.20样例说明
蜗牛路线#xff1a;(0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0)(0,0)→(1,0)→(1,1)→(10,1…问题描述 输入格式 输出格式
输出共一行一个浮点数表示答案四舍五入保留两位小数。
样例输入
3
1 10 11
1 1
2 1样例输出
4.20样例说明
蜗牛路线(0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0)(0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0)花费时间为 110.7011.31≈4.2010.7101.311≈4.20
根据题意可知该题涉及动态规划问题所以我们结合代码进行讲解
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {//第一步接收输入Scanner sc new Scanner(System.in);//n个竹竿int n sc.nextInt();double []x new double[n];//接收n个竹竿的坐标for(int i0;in;i){x[i] sc.nextInt();}//接收从第1跟竹竿到第n-1跟竹竿开始的魔法阵距离double [][] a new double[n-1][2];for(int i0;in-1;i){for (int j 0;j2;j){a[i][j] sc.nextInt();}}//假如直接就可以到达if(n2){System.out.printf(%.2f,x[0]);}//正常多竹竿else {//开始使用动态规划//分两个状态一个使用魔法一个不使用魔法//dp[i][0]不使用dp[i][1]使用//1.确定状态double dp[][] new double[n][2];//2.确定初始值for(int i 0;in;i){Arrays.fill(dp[i],Double.MAX_VALUE);}//不使用魔法到达第一个竹竿dp[0][0] x[0];//使用魔法到达第一个竹竿dp[0][1] x[0];//不使用魔法到达第二个竹竿dp[1][0] x[1];//使用魔法到达第二个竹竿dp[1][1] x[0] a[0][0]/0.7;//3.确定状态转移方程//从第三竹竿到达第n根竹竿的规划for(int i2;in;i){//不使用魔法//前一个不使用魔法dp[i][0] Math.min(dp[i][0],dp[i-1][0] x[i] - x[i-1] );//前一根使用魔法dp[i][0] Math.min(dp[i][0],dp[i-1][1] a[i-2][1]/1.3 x[i] - x[i-1]);//使用魔法dp[i][1] Math.min(dp[i][1],dp[i-1][0] a[i-1][0]/0.7);double k 0.0;if(a[i-2][1] a[i-1][0]){k 1.3;}else k 0.7;//注意我们的要的是差值不是走一整段魔法阵到地面的距离而是两个相邻魔法阵的距离dp[i][1] Math.min(dp[i][1],dp[i-1][1] Math.abs(a[i-2][1] - a[i-1][0])/k);}double result Math.min(dp[n-1][0],dp[n-1][1] a[n-2][1]/1.3);System.out.printf(%.2f,result);}}
}当状态分析好以及状态方程定义好就成功了大半
