杭州市建设网站交换链接平台
问题描述
输入格式
输出格式
输出共一行，一个浮点数表示答案（四舍五入保留两位小数）。
样例输入
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)，花费时间为 1+10.7+0+11.3+1≈4.201+0.71+0+1.31+1≈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 i=0;i<n;i++){x[i] = sc.nextInt();}//接收从第1跟竹竿到第n-1跟竹竿开始的魔法阵距离double [][] a= new double[n-1][2];for(int i=0;i<n-1;i++){for (int j = 0;j<2;j++){a[i][j] = sc.nextInt();}}//假如直接就可以到达if(n<2){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;i<n;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 i=2;i<n;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);}}
}
当状态分析好以及状态方程定义好就成功了大半！