uq_43625241302

用户名：uq_43625241302

访问量：3160

签　名：

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

　　自我简介：

TA的其他文章

预处理 + 双端队列
浏览：365

你可能喜欢

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

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

从记忆化搜索到动态规划

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

13 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

uq_43625241302

TA的其他文章

你可能喜欢

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

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

printf基础练习2 （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

【数组的距离】（C语言代码）

从记忆化搜索到动态规划

评论区

精彩推荐

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

WU-格式化数据输出（C++代码）

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

用筛法求之N内的素数。（C语言代码）

1113题解

A+B for Input-Output Practice (III) （C语言代码）

1071题解

字符串的输入输出处理（C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

1052题解（链表操作）

uq_43625241302

TA的其他文章

你可能喜欢

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

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

printf基础练习2 （C语言代码）

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

【数组的距离】 （C语言代码）

从记忆化搜索到动态规划

评论区

精彩推荐

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

WU-格式化数据输出 （C++代码）

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

用筛法求之N内的素数。 （C语言代码）

1113题解

A+B for Input-Output Practice (III) （C语言代码）

1071题解

字符串的输入输出处理 （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

1052题解（链表操作）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

【数组的距离】（C语言代码）

　　评论区

WU-格式化数据输出（C++代码）

用筛法求之N内的素数。（C语言代码）

字符串的输入输出处理（C语言代码）