第十四届蓝桥杯蜗牛

2024-03-12 09:12
文章标签 蓝桥 第十四届 蜗牛

本文主要是介绍第十四届蓝桥杯蜗牛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蜗牛 线性dp

目录

蜗牛 线性dp

先求到达竹竿底部的状态转移方程

求蜗牛到达第i根竹竿的传送门入口的最短时间​编辑

题目链接：蓝桥杯2023年第十四届省赛真题-蜗牛 - C语言网

关键在于建立数组将竹竿上的每个状态量表示出来，并分析出状态转移方程

  
       int tree []  = new int[n];//记录每根竹竿到原点的距离int portal_exit [] = new int[n];//第i个竹竿上传送门出口高度int portal_entrance [] = new int[n];//第i个竹竿上传送门入口的高度double time_bottom [] = new double[n];//到达第i个竹竿底部的最短时间double time_portal [] = new double[n];//到达第i个竹竿传送门入口的最短时间

注意：到达第i个竹竿传送门入口的最短时间也是，蜗牛传送到第i+1根竹竿传送门出口的最短时间

很明显，代码中表示最状态的数组为 time_bottom[i]表示蜗牛从原点到达第i根竹竿的底部用的最短时间

time_portal[i] 表示蜗牛从原点到达第i根竹竿可以传送到第i+1竹竿的传送门入口 a1的最短1时间

我们需要求出time_bottom[i]和time_poratal[i]的状态转移方程

先求到达竹竿底部的状态转移方程

由图可知

到达第i竹竿底部的方法有两种

（1）从前一个竹竿的底部直接爬过来

time_bottom[i]=time_bottom[i-1]+tree[i]-tree[i-1];

ps:tree[i]-tree[i-1]为蜗牛从前一个竹竿爬过来用的时间

（2）从当前竹竿的传送门出口爬下来

到达第i根竹竿底部的时间=蜗牛到达第i根竹竿的传送门出口的时间（即到达第i-1竹竿传送门入口的时间：time_portal[i-1]）+ 传送门出口到底部距离/下爬速度

time_bottom[i]=time_portal[i-1]+portal_exit[i]/1.3;

综合（1）（2）得time_bottom[i]得状态转移方程

 time_bottom[i]=Math.min(time_bottom[i-1]+tree[i]-tree[i-1],time_portal[i-1]+portal_exit[i]/1.3)
求蜗牛到达第i根竹竿的传送门入口的最短时间

同样有两种方式

（1）从传送门出口爬到传送门入口

如果传送门出口比传送门入口高那么直接向下爬

到达传送门出口的时间+传送门出口-传送门入口的距离/速度

 time_portal[i]=time_protal[i-1]+(portal_exit[i]-portal_entrance[i])/1.3;

如果传送门出口的高度比入口的低那么就要向上1爬速度为0.7

（2）从底部爬到传送门

 time_portal[i]=time_bottom[i]+portal_entrance[i]/0.7;

综上time_portal[i]的状态转移方程为：(传送门出口比传送门入口高的情况)

 ime_portal[i]=Math.min(time_protal[i-1]+(portal_exit[i]-portal_entrance[i])/1.3,time_bottom[i]+portal_entrance[i]/0.7)

最后我们可以给第1根竹竿的状态初始化

 //第一根竹竿的底部和传送出口最短时间我们可以算出来
  time_bottom[0]=tree[0];//1time_portal[0]=tree[0]+portal_entrance[0】；

第n根竹竿我们要特殊判断一下因为最后一根竹竿没有传送门入口

完整代码

import java.util.Scanner;public class Snail {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int tree []  = new int[n];//记录每根竹竿到原点的距离int portal_exit [] = new int[n];//第i个竹竿上传送门出口高度int portal_entrance [] = new int[n];//第i个竹竿上传送门入口的高度double time_bottom [] = new double[n];//到达第i个竹竿底部的最短时间double time_portal [] = new double[n];//到达第i个竹竿传送门入口的最短时间for (int i=0;i<n;i++){tree[i]=sc.nextInt();}for (int i=0;i<n-1;i++){portal_entrance[i]=sc.nextInt();portal_exit[i+1]=sc.nextInt();}
//第一根竹竿的底部和传送出口最短时间我们可以算出来time_bottom[0]=tree[0];//1time_portal[0]=tree[0]+portal_entrance[0]/0.7;//2.4for (int i=1;i<n;i++){
//            给出结束条件if (i==n-1){
//            从上一根竹竿底部直接到第i根竹竿底部double bottom1 = time_bottom[i-1]+tree[i]-tree[i-1];
//                从第i根竹竿的传送门出口向下爬到底部double bottom2 = time_portal[i-1]+portal_exit[i]/1.3;time_bottom[i]=Math.min(bottom1,bottom2);break;}else{//            从上一根竹竿底部直接到第i根竹竿底部double bottom1 = time_bottom[i-1]+tree[i]-tree[i-1];
//                从第i根竹竿的传送门出口向下爬到底部double bottom2 = time_portal[i-1]+portal_exit[i]/1.3;//3.2
//              计算最短到达第i根竹竿底部的距离time_bottom[i]=Math.min(bottom1,bottom2);//3.2
//                计算到达第i根竹竿传送门入口的最短时间
//                到达传送门入口的第一种方式：从底部爬到入口double time_entrance1=time_bottom[i]+portal_entrance[i]/0.7;
//                 到达传送门入口的第二种方式：从传送门的出口爬到入口double time_entrance2=0;if (portal_entrance[i]>=portal_exit[i]){//如果入口在出口上面,向上爬time_entrance2=time_portal[i-1]+(portal_entrance[i]-portal_exit[i])/0.7;}else {time_entrance2=time_portal[i-1]+(portal_exit[i]-portal_entrance[i])/1.3;}
//                从两种方式中取最短时间time_portal[i]=Math.min(time_entrance1,time_entrance2);}}System.out.printf("%.2f",time_bottom[n-1]);}
}

写下血与泪的教训：时间的数据类型一定要用double不然数据量太大精度不够不能通过。

这篇关于第十四届蓝桥杯蜗牛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/800791。

相关文章

C语言蓝桥杯

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s
阅读更多...
找不同-第15届蓝桥省赛Scratch初级组真题第4题

找不同-第15届蓝桥省赛Scratch初级组真题第4题

[导读]：超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成，后续会不定期解读蓝桥杯真题，这是Scratch蓝桥杯真题解析第183讲。 如果想持续关注Scratch蓝桥真题解读，可以点击《Scratch蓝桥杯历年真题》并订阅合集，查阅教程更方便。 第15届蓝桥杯省赛已于2024年8月24日落下帷幕，编程题一共有5题，分别如下： 猪八戒落地 游乐场 画西瓜 找不同 消
阅读更多...
【蓝桥杯嵌入式（一）程序框架和调度器】

【蓝桥杯嵌入式（一）程序框架和调度器】

蓝桥杯嵌入式（一）程序框架和调度器 序、代码命名规则零、STM32和8051⼀、软件及环境安装⼆、⼯程框架搭建1.时钟配置2、SYS配置3、⼯程配置4、NVIC配置5.、Keil配置 三、系统初始化四、任务调度器 链接: 视频出处 序、代码命名规则 以下是一些常见的举例 零、STM32和8051 链接: 8位和32位单片机最本质区别 ⼀、软件及环境安装
阅读更多...
【蓝桥杯嵌入式（二）Led、Key、Lcd】

【蓝桥杯嵌入式（二）Led、Key、Lcd】

蓝桥杯嵌入式（二）Led、Key、Lcd 五、Led模块1.原理图配置2. 知识点3.底层代码 六、Key模块1.原理图配置2.知识点3.底层代码底层代码（四⾏代码版本）底层代码（状态机版本） 七、LCD模块1.原理图配置2.知识点底层代码 五、Led模块 1.原理图配置 2. 知识点 链接: 上拉电阻的通俗解释 链接: 单⽚机怎么输出⾼电平！推挽输出和开
阅读更多...
蓝桥杯：整数删除

蓝桥杯：整数删除

// 蓝桥杯整数删除.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include<stdio.h>#define MAX 100void findmin(int a[],int n,int& pos){int min=a[0];pos=0;//pos=0我开始忘了，特别注意
阅读更多...
第十五届蓝桥杯图形化省赛题目及解析

第十五届蓝桥杯图形化省赛题目及解析

第十五届蓝桥杯图形化省赛题目及解析 一. 单选题 1. 运行以下程序，角色会说( )? A、29     B、31     C、33     D、35 正确答案：C 答案解析： 重复执行直到m>n不成立，即重复执行直到m<=n。所有当m小于或者 等于n时，循环结束。循环过程中变量m与变量n的变化如下表： 通过上述表格可知，循环到第五次循环结束。m的值为14，n的值为19
阅读更多...
第八届蓝桥杯 最大公共子串（动态规划）

第八届蓝桥杯 最大公共子串（动态规划）

标题：最大公共子串 最大公共子串长度问题就是： 求两个串的所有子串中能够匹配上的最大长度是多少。 比如："abcdkkk" 和 "baabcdadabc"， 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。 下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。 请分析该解法的思路，并补全划线部分缺失的代码。 #include <stdio.h
阅读更多...
蓝桥杯第八届 方格分割（dfs)

蓝桥杯第八届 方格分割（dfs)

标题：方格分割6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图：p1.png, p2.png, p3.png 就是可行的分割法。试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。请提交该整数，不要填写任何多余的内容或说明文字。   观察可得他是一个中心对称图形，我们只需要搜索它的对称线即可。我们可以把对称线抽象为从（
阅读更多...
蓝桥杯备赛day02：递推

蓝桥杯备赛day02：递推

斐波那契数列 #include <bits/stdc++.h>using namespace std;int main(){int n;cin>>n;int dp[n+1];dp[1]=1;dp[2]=1;for(int i = 3;i <= n;i++) dp[i] = dp[i-1]+dp[i-2];cout<<dp[n];return 0;} n = int(input())
阅读更多...
蓝桥杯入门训练——序列求和

蓝桥杯入门训练——序列求和

入门训练 序列求和   时间限制：1.0s   内存限制：256.0MB         问题描述 求1+2+3+...+n的值。 输入格式 输入包括一个整数n。 输出格式 输出一行，包括一个整数，表示1+2+3+...+n的值。 样例输入 4 样例输出 10 样例输入 100 说明：有一些试题会给出多组样例输入输出以帮助你更好的做题。 一般在提
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2