uq_43625241302

用户名：uq_43625241302

访问量：393

签　名：

等　　级
排　　名	13209
经　　验	750
参赛次数	1
文章发表	5
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

模拟分类（标题不能太短）
浏览：81

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

从记忆化搜索到动态规划

　　作者: uq_43625241302　　　　发表时间：2023-04-23 18:17:55 浏览：106　|　评论：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分

2 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

uq_43625241302

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C二级辅导-求偶数和（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

点我有惊喜！你懂得！

从记忆化搜索到动态规划

评论区

精彩推荐

汽水瓶（C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （Java代码）

C语言训练-列出最简真分数序列* （C语言代码）

C二级辅导-进制转换（C语言代码）

C语言训练-最大数问题（C语言代码）

淘淘的名单（C语言代码）答案错误？？？

计算质因子（C++代码）

输出正反三角形（C语言代码）

蛇行矩阵（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

uq_43625241302

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

点我有惊喜！你懂得！

从记忆化搜索到动态规划

评论区

精彩推荐

汽水瓶 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （Java代码）

C语言训练-列出最简真分数序列* （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言训练-最大数问题 （C语言代码）

淘淘的名单 （C语言代码）答案错误？？？

计算质因子 （C++代码）

输出正反三角形 （C语言代码）

蛇行矩阵 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-求偶数和（C语言代码）

　　评论区

汽水瓶（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言训练-最大数问题（C语言代码）

淘淘的名单（C语言代码）答案错误？？？

计算质因子（C++代码）

输出正反三角形（C语言代码）

蛇行矩阵（C语言代码）