Java实现 蓝桥杯 算法提高 秘密行动
2024-09-07 13:52:47
试题 算法提高 秘密行动
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
小D接到一项任务,要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点,每层的高度都不一样,同时,小D也拥有一项特殊能力,可以一次向上跳跃一层或两层,但是这项能力无法连续使用。已知向上1高度消耗的时间为1,跳跃不消耗时间。由于事态紧急,小D想知道他最少需要多少时间到达顶层。
输入格式
第一行包含一个整数n,代表楼的高度。
接下来n行每行一个整数ai,代表i层的楼层高度(ai <= 100)。
输出格式
输出1行,包含一个整数,表示所需的最短时间。
样例输入
5
3
5
1
8
4
样例输出
1
数据规模和约定
对20%的数据,n<=10
对40%的数据,n<=100
对60%的数据,n<=5000
对100%的数据,n<=10000
import java.util.Scanner;
public class 秘密行动 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [] num = new int [n];
for (int i=0;i<n;i++){
num[i]=sc.nextInt();
}
sc.close();
int [] []dp = new int [n+1][2];
//第一个爬上来的是第一层的长度
dp[1][0]=num[0];
//跳上来的长度为0
for (int i=2;i<=n;i++){
//dp[i][0]就是爬上来的所以要加长度,跳完爬或者爬完继续爬
dp[i][0]=Math.min(dp[i-1][0],dp[i-1][1])+num[i-1];
//dp[i][1]是跳上来得到,他只能在爬上来的里面选
dp[i][1]=Math.min(dp[i-1][0],dp[i-2][0]);
}
System.out.println(Math.min(dp[n][0],dp[n][1]));
}
}
最新文章
- JQuery 绑定select标签的onchange事件,弹出选择的值,并实现跳转、传参
- zabbix3.0.4 部署之七 (zabbix3.0.4 邮件报警) &; 微信报警
- 将Jquery序列化后的表单值转换成Json
- ef to sqlite 实际开发问题终极解决方法
- oracle函数,查询,事务
- 【你吐吧c#每日学习】11.10 C# Data Type conversion
- GenericServlet,HttpServletRequest和HttpServletResponse
- (转)Python JSON序列化
- tomcat下context.xml中JNDI数据源配置
- Android实例-消息框(XE8+小米2)
- [转] Git 分支 - 分支的新建与合并
- Android官方技术文档翻译——Apk 拆分机制
- 基于promise对小程序http请求方法封装
- 光刻技术的原理和EUV光刻技术前景
- Mark SDL2 Lazy Foo&#39;s Producations
- SSM框架mapper.xml模糊查询语句
- httpclient的调用 发送json字符串
- ssm又乱码
- Springboot定时任务原理及如何动态创建定时任务
- ubuntu1604使用之旅——安装samba