首页 > 其他分享 >奇怪的电梯

奇怪的电梯

时间:2024-05-16 13:54:21浏览次数:17  
标签:cnt le evlt int 电梯 ans 奇怪

传送锚点:https://www.luogu.com.cn/problem/P1135

题目描述

呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 $i$ 层楼($1 \le i \le N$)上有一个数字 $K_i$($0 \le K_i \le N$)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: $3, 3, 1, 2, 5$ 代表了 $K_i$($K_1=3$,$K_2=3$,……),从 $1$ 楼开始。在 $1$ 楼,按“上”可以到 $4$ 楼,按“下”是不起作用的,因为没有 $-2$ 楼。那么,从 $A$ 楼到 $B$ 楼至少要按几次按钮呢?

输入格式

共二行。

第一行为三个用空格隔开的正整数,表示 $N, A, B$($1 \le N \le 200$,$1 \le A, B \le N$)。

第二行为 $N$ 个用空格隔开的非负整数,表示 $K_i$。

输出格式

一行,即最少按键次数,若无法到达,则输出 -1

样例 #1

样例输入 #1

5 1 5
3 3 1 2 5

样例输出 #1

3

提示

对于 $100 %$ 的数据,$1 \le N \le 200$,$1 \le A, B \le N$,$0 \le K_i \le N$。

本题共 $16$ 个测试点,前 $15$ 个每个测试点 $6$ 分,最后一个测试点 $10$ 分。

思路

此题我们要优化我们的剪枝方案,引入ans统计从起点到该层最小按键次数,若cnt + 1大于等于到达该层的最小按键次数,直接剪枝,进行优化

code

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 210;
int n,a,b;
int evlt[maxn];//存储电梯初始数字
int res = 1e9;//最少按键次数
int ans[maxn];//记录从起点到此层的最小按键次数 
void dfs(int x, int cnt) {//x代表第几层,cnt为按的次数
	ans[x] = cnt;
	//上 
	if (x - evlt[x] > 0 && cnt + 1 < ans[x - evlt[x]] ) {
		dfs(x - evlt[x], cnt + 1);
	}
	//下 
	if (x + evlt[x] <= n && cnt + 1 < ans[x + evlt[x]]) {
		dfs(x + evlt[x], cnt + 1);
	}
}
int main()
{
	cin >> n >> a >> b;
	memset(ans,0x7f,sizeof(ans));//0x7f为127,作为初始化状态 
	for (int i = 1; i <= n; i++) {
		cin >> evlt[i];
	}
	dfs(a, 0);
//ans整数数组,每个整数占用4个字节,初始化时,每个整数的每个字节都会被设置为0x7f, 
	if(ans[b] != 0x7f7f7f7f){//判断ans[b]是否被计算过 
		cout << ans[b];
	}
	else cout << -1;

	return 0;
}

标签:cnt,le,evlt,int,电梯,ans,奇怪
From: https://www.cnblogs.com/6Luffy6/p/18195818

相关文章

  • 复杂网络社区发现算法聚类分析全国电梯故障数据和可视化:诊断电梯“安全之殇”|附代码
    参考原文:http://tecdat.cn/?p=2186最近我们被客户要求撰写关于复杂网络社区发现算法的研究报告,包括一些图形和统计输出。物业工程肩负着维持项目各类设施设备的正常运作,保障全体业主的正常生活,令物业保值升值,是项目的心脏部门。拓端数据(tecdat)研究人员根据全国电梯故障上报汇总......
  • 电梯会议+原型展示
    视频效果展示:原型展示PPT:......
  • 团队博客——电梯演讲与原型说明
    原型展示:团队名称-成员人数:sigma-4所选领域:领域一:社区公益作品创意介绍:当今时代下,恶劣的校园霸凌现象时常发生,但是被霸凌者往往因为害怕或者威胁,不敢向自己的亲人或者老师反应霸凌现象。身处互联网时代下,被霸凌者大概率会在网上吐露心声,我们这款软件便应运而生。主要功能:聊......
  • 一些奇奇怪怪的js知识
    0.关于前端为什么typeofnull得到的结果是object对于null来说,很多人会认为他是个对象类型,其实这是错误的。虽然`typeofnull`会输出`object`,但是这只是JS存在的一个悠久Bug。在JS的最初版本中使用的是32位系统,为了性能考虑使用低位存储变量的类型信息,`000`开头代......
  • 奇怪的电梯
    题目描述: 思路:见代码注释AC代码:#include<bits/stdc++.h>usingnamespacestd;intn,A,B;intt[250];//记录到达每层所用的最短时间inta[250];voiddfs(intlou,intsum){ //lou是当前的楼层数,sum为当前按键次数 t[lou]=sum;//先进行赋值 //下 if(......
  • 奇怪的错误-------重新定义一下变量就不报错了
    1packagecom.lian.mysqldemo2;23importandroidx.appcompat.app.AppCompatActivity;45importandroid.os.Bundle;6importandroid.os.Handler;7importandroid.text.TextUtils;8importandroid.view.View;9importandroid.widget.TextView;1011......
  • 第六个OpenGL程序,Coordinate Systems 坐标系统 后续之 3D 1(这个图形有点奇怪)
    效果:代码main.cpp:#include<iostream>#include<glad/glad.h>#include<glfw3.h>#include"Shader.h"#defineSTB_IMAGE_IMPLEMENTATION#include<stb_image.h>#include<glm/glm.hpp>#include<glm/gtc/matrix_transfo......
  • P1135 奇怪的电梯 (双向bfs)
    输入输出样例输入 51533125输出3说明/提示对于 100%100% 的数据,1≤N≤200,1≤A,B≤N,0≤Ki​≤N。本题共 1616 个测试点,前 1515 个每个测试点 66 分,最后一个测试点 10 分。1.重写AC代码:将步数记录在结构体中#include<algorithm>#include<iostream......
  • [20240321]分析FORCE_MATCHING_SIGNATURE重合的奇怪情况.txt
    [20240321]分析FORCE_MATCHING_SIGNATURE重合的奇怪情况.txt--//生产系统遇到1个FORCE_MATCHING_SIGNATURE重合的奇怪现象,一般情况都是相似的sql语句(没有使用绑定变量的sql语句),--//FORCE_MATCHING_SIGNATURE相同。--//注:11g之前如果绑定变量与常量混合,会出现EXACT_MATCHING_SIGN......
  • 奇奇怪怪的任意用户注册
    免责声明:由于传播、利用本文章所提供的信息而造成的任何直接或者间接的后果及损失,均由使用者本人负责,作者不为此承担任何责任,一旦造成后果请自行承担!如有侵权烦请告知,我们会立即删除并致歉。谢谢!又他妈起床上B班我艹了,一早发一网站让我测试。。。开局登入框,点击密码找回测试......