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

1693 阅读 1 评论 0 点赞

原题链接：蓝桥杯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分

7 人评分

本文分类：题解列表
浏览次数：1693 次浏览
发布日期：2023-04-21 00:24:27
本文链接：https://blog.dotcpp.com/a/96005

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

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

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

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

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

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

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

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

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

评论列表共有 1 条评论

发表评论取消回复

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

一笔画问题（dfs）

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

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

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

评论列表 共有 1 条评论

发表评论 取消回复

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

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

评论列表共有 1 条评论

发表评论取消回复