怪兽

用户名：uq_40659356218

访问量：751

签　名：

等　　级
排　　名	11549
经　　验	1020
参赛次数	0
文章发表	12
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

dp解法[y总解法]
浏览：96

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）和1002的题目是一样的

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

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

dp解法[y总解法]

　　作者: 怪兽　　　　发表时间：2024-04-01 19:11:20 浏览：96　|　评论：0　

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

看了y总分析才写出来
```
import java.util.Scanner;

public class Main {
	static int N;
	static int[] arr;
	static int[] x;
	static int[] a = new int[100001];
	static int b[] = new int[100001];
    //a[i] 记录第i根竹竿的到下一个杆传送门的位置
	//b[i] 记录第i-1根竹竿传送到第i根竹竿时的位置
	//dp[i][0] 记录 到第i根杆子底部（xi，0）的最短时间 
	//dp[i][1] 记录到第i-1根杆子的传送门 即 第i根杆上传送点的最短时间
	static double [][]dp;
	static double get(int x1, int x2) {
		if(x1>x2) return (x1-x2)/1.3;
		else  return(x2-x1)/0.7;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		x = new int[N + 2];
		dp = new double[N+2][2];
		for (int i = 1; i <= N; i++) {
			x[i] = sc.nextInt();
		}
		for (int i = 1; i <= N - 1; i++) {
			a[i] = sc.nextInt();
			b[i + 1] = sc.nextInt();
		}
		for(int i = 1 ;i<=N;i++){
		    dp[i][0] = dp[i][1] =Double.MAX_VALUE;
		}
		dp[1][0] = x[1]/1.0;
		 
		for(int i = 2;i<= N;i++) {
		    int d = x[i]-x[i-1];
			dp[i][0] = Math.min(
					dp[i-1][0]+d,
					dp[i-1][1]+get(b[i-1],0)+d
					); //到第i根杆的底部有两种走法 从第i-1根杆沿着X轴走 或 从i-1传送点开始先往下走再沿着x轴走
			dp[i][1] = Math.min(
					dp[i-1][0]+a[i-1]/0.7,
					dp[i-1][1]+get(b[i-1],a[i-1])
					); //到第i根杆上有两种走法 从第i-1根杆子底部走到第i根底部再往上爬 或 从第i-1根传送
		}
		System.out.printf("%.2f",Math.min(dp[N][0], dp[N][1]+b[N]/1.3));

}

```

到第i根杆底部的走法不包括从i-1根杆子传送过来再往下走 这种走法会与 dp [i] [1] 有重合

0.0分

0 人评分

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

怪兽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）和1002的题目是一样的

不容易系列（C语言代码）

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

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

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

dp解法[y总解法]

评论区

精彩推荐

校门外的树（C语言代码）

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

钟神赛车（C++代码）

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

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

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

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

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

C语言考试练习题_一元二次方程（C语言代码）

怪兽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）和1002的题目是一样的

不容易系列 （C语言代码）

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

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

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

dp解法[y总解法]

评论区

精彩推荐

校门外的树 （C语言代码）

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

钟神赛车 （C++代码）

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

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

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

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

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

C语言考试练习题_一元二次方程 （C语言代码）

不容易系列（C语言代码）

　　评论区

校门外的树（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

钟神赛车（C++代码）

C语言考试练习题_一元二次方程（C语言代码）