当前位置:   article > 正文

蓝桥杯---蜗牛【动态规划典型题目】

蓝桥杯---蜗牛【动态规划典型题目】

题目链接:蜗牛

  1. import java.util.*;
  2. public class Main {
  3. public static void main(String[] args) {
  4. Scanner scanner=new Scanner(System.in);
  5. int n=scanner.nextInt();
  6. int[] x=new int[n+1];
  7. for(int i=1;i<=n;i++){
  8. x[i]=scanner.nextInt();
  9. }
  10. int[] a=new int[n+1];
  11. int[] b=new int[n+2];
  12. for(int i=1;i<=n-1;i++){
  13. a[i]=scanner.nextInt();//表示第i个柱子的传送起点高度
  14. b[i+1]=scanner.nextInt();//表示第i个柱子被传送后到的高度
  15. }
  16. double[][] dp=new double[n+1][2];//dp[i][0]表示第i个节点的时间,dp[i][1]表示到达第i个传送门的时间
  17. dp[1][0]=x[1];
  18. dp[1][1]=x[1]+a[1]/0.7;
  19. for(int i=2;i<=n;i++){
  20. if(a[i]>=b[i]){
  21. //第i个传送门位置=min(上一个节点所需的时间然后直接走到下一个柱子,再爬上传送门的时间,上一个传送门时间,然后直接传送过来,在判断当前传送到的高度和该柱子可以传送的高度)
  22. dp[i][1]=Math.min(dp[i-1][0]+x[i]-x[i-1]+a[i]/0.7,dp[i-1][1]+(a[i]-b[i])/0.7);
  23. }
  24. else{
  25. dp[i][1]=Math.min(dp[i-1][0]+x[i]-x[i-1]+a[i]/0.7,dp[i-1][1]+(b[i]-a[i])/1.3);
  26. }
  27. //第i个节点时间=min(上一个节点所需时间,加上直接走过来的时间,上一个传送门的时间,然后传送过来,在计算下落到高度0的时间)
  28. dp[i][0]=Math.min(dp[i-1][1]+b[i]/1.3,dp[i-1][0]+x[i]-x[i-1]);
  29. }
  30. System.out.printf("%.2f",dp[n][0]);
  31. }
  32. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/766035
推荐阅读
相关标签
  

闽ICP备14008679号