迷你滨

用户名：uq_20629230267

访问量：1305

签　名：

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

　　自我简介：

TA的其他文章

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

蓝桥杯2023年第十四届省赛真题-合并石子（区间dp）
浏览：89

蓝桥杯2023年第十四届省赛真题-魔法阵(最短路+简单dp)
浏览：89

你可能喜欢

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

　　作者: 迷你滨　　　　发表时间：2023-04-21 00:24:27 浏览：280　|　评论：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分

3 人评分

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

迷你滨

TA的其他文章

你可能喜欢

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

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

【回文数(二)】（C语言代码）

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

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

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

评论区

精彩推荐

众数问题（C语言代码）

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

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

有关字符，字符串的输入输出函数说明

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

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

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

C语言训练-排序问题<1> （C语言代码）

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

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

迷你滨

TA的其他文章

你可能喜欢

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

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

【回文数(二)】 （C语言代码）

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

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

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

评论区

精彩推荐

众数问题 （C语言代码）

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

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

有关字符，字符串的输入输出函数说明

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

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

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

C语言训练-排序问题<1> （C语言代码）

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

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

【回文数(二)】（C语言代码）

　　评论区

众数问题（C语言代码）