蓝桥杯 秘密行动

news/2024/5/20 21:26:35

问题描述
  小D接到一项任务,要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点,每层的高度都不一样,同时,小D也拥有一项特殊能力,可以一次向上跳跃一层或两层,但是这项能力无法连续使用。已知向上1高度消耗的时间为1,跳跃不消耗时间。由于事态紧急,小D想知道他最少需要多少时间到达顶层。
输入格式
  第一行包含一个整数n,代表楼的高度。

接下来n行每行一个整数ai,代表i层的楼层高度(ai <= 100)。
输出格式
  输出1行,包含一个整数,表示所需的最短时间。
样例输入
5
3
5
1
8
4
样例输出
1

问题分析:
首先根据题意有两个状态,爬楼和跳跃,并且不能连续跳
跃,所以用两个状态表示跳跃(T[i])和爬楼P[i],那么
对于跳跃状态的路程T[i] = min(p[i - 1], p[i - 2])
(因为跳跃状态上一步只能是爬)
对于爬楼状态P[i] = min(T[i - 1], P[i - 1]) + a[i](
当前楼层高度)
(因为下一状态依旧可以跳跃,所以上一步可以是跳跃,
也可以是爬楼)
最后最短的路程就是min(P[i] , T[i])

在这里插入图片描述

#include <algorithm>
#include <iostream>
#include <string.h> 
using namespace std;
int a[10010];
int P[10010]; //爬楼状态 
int T[10010];//跳楼状态 int main () {int n;cin >> n;for (int i = 1; i <= n; i ++) {cin >> a[i];}P[1] = a[1];for (int i = 2; i <= n; i ++) {P[i] = min(P[i - 1], T[i - 1]) + a[i];T[i] = min(P[i - 1], P[i - 2]);}cout << min(P[n], T[n]);return 0;
}

https://www.xjx100.cn/news/848181.html

相关文章

JZOJ3348. 【NOI2013模拟】秘密任务

Description 给定无向图&#xff0c;有边权和点权&#xff0c;删去一条边的代价为这条边的任意一个顶点的权值&#xff0c;求一个最小代价的删边方案&#xff0c;使得1到n的在原图中的最短路都被断开。问最小代价&#xff0c;以及这个方案是否唯一。2 ≤ N ≤ 400, 1 ≤ M ≤ …

比亚迪、理想冒头背后,混动完胜纯电动?

进入六月份&#xff0c;各家车企的五月销量成绩陆续出炉了&#xff0c;差距也再次拉大。其中&#xff0c;比亚迪以23.9万辆的销售成绩再次夺得冠军&#xff0c;特斯拉中国则突破了单月7.5万辆&#xff0c;广汽埃安也首次突破了单月4.5万辆&#xff0c;上汽乘用车则上升至第四位…

bzoj 3258 秘密任务

http://www.elijahqi.win/archives/3689 Description Alice听说在一片神奇的大陆MagicLand&#xff0c;有一个古老的传说……很久很久以前&#xff0c;那个时候 MagicStates共和国刚刚 成立。 反对新政府的势力虽已被镇压&#xff0c;但仍然在暗地活动。这一次&#xff0c;情报…

秘密任务

秘密任务 Description Input 第一行 包含一 个正整数 T&#xff0c;表示有 T组测试数据。接下来 依次是 T组测试数 据。 每组测试数 据的第一行包含两个整N、M。 第二行包含 N - 1个正整数&#xff0c;依次表示 A1&#xff0c;A2&#xff0c; …&#xff0c;AN-1。 接下来…

​如何高效开发一个OA办公系统​?

如何才能高效开发一个OA办公系统&#xff1f;这篇教你使用零代码工具从0-1搭建一个OA办公系统&#xff0c;无需代码基础&#xff0c;只要你懂业务&#xff0c;只需3步即可搭建&#xff01; 先来看看效果—— 系统模板>> https://www.jiandaoyun.com/ 整个系统包含物资管…

RaaS(勒索软件即服务)是什么?这个模型是如何工作的?

Ransomware as a Service是一个英语术语,指的是一种商业模型&#xff0c;其中勒索软件开发者向感兴趣的恶意行为者提供工具&#xff0c;以便他们可以发起勒索软件攻击。使用者通过签约创建恶意软件即服务或加入联盟计划&#xff0c;并分发一系列勒索软件以换取一定比例的利润。…

Vue中如何进行表格合并与拆分

Vue中如何进行表格合并与拆分 在Vue应用程序中&#xff0c;表格是一个非常常见的组件。有时候我们需要对表格进行合并或拆分来满足特定的需求。在本文中&#xff0c;我们将介绍如何在Vue中进行表格的合并和拆分。 如何进行表格合并&#xff1f; 表格合并是指将多行或多列的单…

java企业级开发1

java web开发入门基础 什么是静态&#xff1f;什么是动态&#xff1f;网页的发展史 静态web资源&#xff08;如html页面&#xff09;&#xff1a;指web页面中提供给人们浏览的数据始终是不变的。 动态web资源&#xff08;如jsp&#xff0c;php等&#xff09;&#xff1a;指w…