思路:
用dp来记录最短消耗时间
dp[坐标][zhuangtai]
状态0表示在底部,状态1表示在传送门处;
先初始化dp[1][0] 和dp[1][1]然后循环遍历到dp[n][0] 和dp[n][1],用动态规划方程去赋值;
ps:易错点在于要开到dp[n+1][2],不然会段错误,然后就是传送门传送后不是立刻就到下一个i的传送门处这是一直我没发现bug的地方即不用把方程简单写成dp[i][1]=dp[i-1][1],他们出来还是有可能有一定距离的得往上爬或者往下滑
更多的解题思路放在代码里了可以详细看一下:
import java.util.*;
public class Main {
public static void main(String []args) {
int n;
Scanner scan = new Scanner(System.in);
n = scan.nextInt();//n根竹竿
int []z = new int[n+1];//竹竿横坐标
int []a = new int[n+1];//a的纵坐标
int []b = new int[n+1];//b的纵坐标
for(int i=1;i<n+1;i++) {
z[i] = scan.nextInt();
}
for(int i=1;i<n;i++) {
a[i] = scan.nextInt();
b[i+1] = scan.nextInt();
}
//创建二维dp数组
double [][]dp = new double[n+1][2];
dp[1][0]=z[1];//走到第一根竹竿的底部时间
dp[1][1]=z[1]+a[1]/0.7;//走到第一传送阵的时间
//填充dp数组
//ps:左边的一定是未知,右边的是已知不能直接写
for(int i=2;i<=n;i++) {
//1.首先因为上升和下降速度不一样,可以先判断a[i]和b[i]的相对位置(同一根竹竿出传送门和进传送门的位置信息)
//dp[i][0]有两种来源:1.dp[i][0]=dp[i-1][0]+z[i]-z[i-1]//不走传送门直接底部走
// 2.dp[i][0]=dp[i-1][1]+b[i]/1.3//传送阵加滑下来时间
//dp[i][1]有两种来源:1.dp[i][1]=dp[i-1][1]
// 2.dp[i][1]=dp[i][0]+a[i]
dp[i][0] = Math.min(dp[i-1][0]+z[i]-z[i-1], dp[i-1][1]+b[i]/1.3);
if(a[i]>b[i]&&i!=n) {
dp[i][1] = Math.min(dp[i-1][1]+(a[i]-b[i])/0.7, dp[i][0]+a[i]/0.7);
}
else if(a[i]<=b[i]&&i!=n) {
dp[i][1] = Math.min(dp[i-1][1]+(b[i]-a[i])/1.3, dp[i][0]+a[i]/0.7);
}
// if(a[i]>b[i]){
// dp[i][1] = Math.min(dp[i-1][0] + z[i]-z[i-1] + a[i]/0.7, dp[i-1][1] + (a[i]-b[i])/0.7);
// }else {
// dp[i][1] = Math.min(dp[i-1][0] + z[i]-z[i-1] + a[i]/0.7,dp[i-1][1] + (b[i]-a[i]) /1.3);
// }
// dp[i][0] = Math.min(dp[i-1][1] +b[i]/1.3 ,dp[i-1][0]+z[i]-z[i-1]);
}
System.out.printf("%.2d",dp[n][0]);
}
}