迷你滨

用户名：uq_20629230267

访问量：9282

签　名：

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

　　自我简介：

TA的其他文章

蓝桥杯2023年第十四届省赛真题-网络稳定性(最大生成树+LCA)
浏览：1425

你可能喜欢

蓝桥杯2023年第十四届省赛真题JavaB-蜗牛（线性dp）

　　作者: 迷你滨　　　　发表时间：2023-04-21 00:24:27 浏览：1254　|　评论：1　

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

### 蓝桥杯2023年第十四届省赛真题-蜗牛（线性dp）
dp[i][j] 表示蜗牛走到第 i 根杆子的最短用时，j 表示状态。
j = 0 : 走到杆子底部
j = 1 ：走到杆子的传送门处
P.S.由于只与前一个杆子状态有关，其实用两个变量就行，用二维数组便于理解
时间复杂度: O(n)
```Java
import java.io.*;
import java.util.*;

public class Main{
	static int maxn = 200005,n,m;
	static long INF = (long)2e18,ans = 0,mod = (int)1e9+7;
	static Scanner sc = new Scanner (System.in);
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st  =new StreamTokenizer(bf);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[]args) throws IOException{
    	int T = 1;
    	//T = Integer.parseInt(S());
    	while(T-->0) solve();
        pw.flush();
    }
    static final int I() throws IOException {
    	st.nextToken();
    	return (int)st.nval;
    }
    
    static void solve() throws IOException{
    	n = I();
    	long x[] = new long [n+1];
    	for(int i=1;i<=n;i++) x[i] = I();
    	int []a = new int [n+1];
    	int []b = new int [n+1];
    	for(int i=1;i<n;i++) {
    		a[i] = I();b[i] = I();
    	}
    	double dp[][] = new double[n+1][2];
    	dp[1][0] = x[1]; //底端最小用时
    	dp[1][1] = x[1] + a[1] / 0.7;  //传送门用时
    	for(int i=2; i<=n ; i++) {
    		dp[i][0] = Math.min(dp[i-1][0]+x[i]-x[i-1], dp[i-1][1] + b[i-1]/1.3);
    		dp[i][1] = Math.min(dp[i][0] + a[i] / 0.7, dp[i-1][1] + ((b[i-1]>a[i])?(b[i-1]-a[i])/1.3: (a[i]-b[i-1])/0.7));
    	}
    	pw.printf("%.2f",dp[n][0]);
    	
    }
}
```

0.0分

10 人评分

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

　　评论区

CodingMe

膜拜大佬，终于看懂了！除了把快速输入的方法封装了，提高代码复用率，其他代码还及其精简，真的是诗一样的代码啊

2024-03-26 20:53:20

迷你滨

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

简单的a+b （C语言代码）

C二级辅导-统计字符（C语言代码）

程序员的表白（C语言代码）

printf基础练习2 （有点不明白）

蓝桥杯2023年第十四届省赛真题JavaB-蜗牛（线性dp）

评论区

精彩推荐

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

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

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

妹子杀手的故事（C语言代码）

Quadratic Equation （C语言代码）

交换Easy （C语言代码）

简单的a+b （C语言代码）

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

上车人数（C语言代码）

1250题解

迷你滨

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

简单的a+b （C语言代码）

C二级辅导-统计字符 （C语言代码）

程序员的表白 （C语言代码）

printf基础练习2 （有点不明白）

蓝桥杯2023年第十四届省赛真题JavaB-蜗牛（线性dp）

评论区

精彩推荐

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

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

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

妹子杀手的故事 （C语言代码）

Quadratic Equation （C语言代码）

交换Easy （C语言代码）

简单的a+b （C语言代码）

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

上车人数 （C语言代码）

1250题解

母牛的故事（C语言代码）

C二级辅导-统计字符（C语言代码）

程序员的表白（C语言代码）

　　评论区

妹子杀手的故事（C语言代码）

上车人数（C语言代码）