从记忆化搜索到动态规划

1052 阅读 0 评论 0 点赞

原题链接：蓝桥杯2023年第十四届省赛真题-蜗牛

# 记忆化搜索
## 解题思路
思考：蜗牛在到达一根竹竿时，可能在竹竿的什么位置？
* 第一种：位于竹竿的底部
* 第二种：位于上一个传送门的终点位置

思考：蜗牛在离开一根竹竿时，可能会在竹竿的什么位置？
* 第一种：位于竹竿的的底部
* 第二种：位于当前传送门的起点位置

由上，可以发现一个状态可以由当前竹竿编号和到达竹竿的位置（即高度）确定。
因此，定义一个函数`double dfs(strat, h)`来表示从当前位置出发，到达终点所需要的最短时间。
最终的答案就是`dfs(0, 0) + 第一根竹竿的x坐标`

## 复杂度分析
由于本题是数据量过大，记忆化过不了，因此需要进一步优化

# 转换成递推：动态规划
设 x1 表示从起始位置到当前在竹竿底部所需要的最短时间
设 x2 表示从起始位置到当前到达竹竿传送门起点位置的最短时间
则有
`x1 = min(两根竹竿的距离差 + x1, x2 + 上一个门终点高度 / 1.3)`
`x2 = min(两根竹竿的距离差 + x1 + 当前门起点高度 / 0.7, 上一个门终点到当前门所需要的时间 + x2)`
最后的目标是遍历到终点的 x1
## 代码实现
```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }

if(n == 1) {
            System.out.printf("%.2f", (double) nums[0]);
            return;
        }

int[][] door = new int[n - 1][2];
        for(int i = 0; i < n - 1; i++) {
            door[i][0] = sc.nextInt();
            door[i][1] = sc.nextInt();
        }

// x1 表示到下一个杆子，纵坐标为0的地方所需要的最短时间。
        // x2 表示到下一个传送门的地方所需要的最短时间
        double x1 = nums[0], x2 = nums[0] + door[0][0] / 0.7;
        for(int i = 1; i < n; i++) {
            int d = nums[i] - nums[i - 1];
            double y1 = Math.min(d + x1, x2 + door[i - 1][1] / 1.3);
            if(i == n - 1) {
                System.out.printf("%.2f", y1);
                return;
            }
            x2 = Math.min(d + x1 + door[i][0] / 0.7, x2 + (door[i][0] > door[i - 1][1] ? (door[i][0] - door[i - 1][1]) / 0.7 : (door[i - 1][1] - door[i][0]) / 1.3));
            x1 = y1;
        }
    }
}
```
## 复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)，用于数组的存储

0.0分

7 人评分

本文分类：题解列表
浏览次数：1052 次浏览
发布日期：2023-04-23 18:17:55
本文链接：https://blog.dotcpp.com/a/96091

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

从记忆化搜索到动态规划

评论列表共有 0 条评论

发表评论取消回复

从记忆化搜索到动态规划

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复