`
tiankonguse
  • 浏览: 16375 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

2014年北京网络赛 Instrusive HDU 5040 题解 优先队列

阅读更多

网赛的时候看了这道题,发现就是平常的那种基础搜索题。

 

由于加了一个特殊条件:可以一次消耗3秒或原地停留1秒。

 

那就不能使用简单的队列了,需要使用优先队列才行。

 

题意

 

告诉一副地图:一个起点,一个终点,若干墙,若干监视器,剩下的是空地。

 

起点,终点,监视器都算空地。

监视器初始值会指定一个方向,共有四个方向。

监视器每秒顺时针转动到下个方向。

监视器视野距离为2.

在监视器的位置或在监视器面向的格子是监视区域。

 

普通的移动一格需要消耗1秒时间。

在监视器下移动一格需要消耗3秒时间。

如果呆在原地不动,即使在监视器视野内也不会被发现。

 

求最少时间从起点到达终点。

不能到达输出-1。


思路

 

第一步显然是先算算是不是可以到达终点,直接按在监视器下移动即可。

如果可以到达终点,我们由起点出发

每个点在每个方向有三个选择,之后就不会再处理这个格子。

1.直接走

2.按在监视器下走

3.停一秒后直接走。

 

如果可以直接走,一定不会选择其他的方法,因为同样到达下个位置,其他的方法用时更长。

用时1秒。

 

不能直接走时,我们可以选择在监视器下走。

用时3秒。

当我们停一秒时,如果可以直接走,那就走。如果不能直接走,那我们就放弃停一秒这个选择。

因为停一秒还在监视下,那只好再停一秒或者按监视下走,这两个选择都不会再最开始就在监视下走更优。 

用时2秒。


当我们在这里得到下一个格子的位置和时间的时候,我们还不能马上标记格子访问过。

因为我们有按监视下走的,可能还有某个不按监视下走也到达那个位置的情况。



所以我们只好先把遇到的所有情况扔到优先队列中,在出对时判断就行了。


详见代码

 

详见我的github ( tiankonguse ) :https://github.com/tiankonguse/ACM/blob/master/hdu/5040.cpp

 

这篇博客与 tiankonguse 的个人网站保持同步 http://tiankonguse.com/record/record.php?id=707
 
0
0
分享到:
评论

相关推荐

    仅报头,非侵入性和无宏的运行时反射系统在c++ - skyypjack /meta

    在C++编程中,反射(Reflection)是一种强大的技术,它允许程序在运行时检查自身的行为和结构。在C++标准库中,反射并不是一个内置特性,但开发者们通过各种方式来实现这一功能,以增强代码的灵活性和可扩展性。...

    第11讲:深入理解指针(1).pdf

    第11讲:深入理解指针(1)

    springboot整合 freemarker方法

    springboot整合 freemarker方法

    第14讲:深入理解指针(4).pdf

    第14讲:深入理解指针(4)

    同行者4.1.2语音助手

    《同行者4.1.2语音助手:车机版安装详解》 在现代科技日新月异的时代,智能车载设备已经成为了汽车生活的重要组成部分。"同行者4.1.2"便是这样一款专为车机设计的语音助手,旨在提供更为便捷、安全的驾驶体验。该版本针对掌讯全系列设备进行了兼容优化,让车主能够轻松实现语音控制,减少驾驶过程中的手动操作,提升行车安全性。 我们来了解下"同行者4.1.2"的核心功能。这款语音助手集成了智能语音识别技术,用户可以通过简单的语音指令完成导航、音乐播放、电话拨打等一系列操作,有效避免了因操作手机或车机带来的分心。此外,其强大的语义理解和自学习能力,使得它能逐步适应用户的口音和习惯,提供更个性化的服务。 在安装过程中,用户需要注意的是,"同行者4.1.2"包含了四个核心组件,分别是: 1. TXZCore.apk:这是同行者语音助手的基础框架,包含了语音识别和处理的核心算法,是整个应用运行的基础。 2. com.txznet.comm.base.BaseApplication.apk:这个文件可能包含了应用的公共模块和基础服务,为其他组件提供支持。 3. TXZsetting.apk:这

    市场拓展主管绩效考核表.xls

    市场拓展主管绩效考核表

    “线上购车3D全方位体验:汽车模型展示与个性化定制功能”,three.js案例- 线上购车3d展示(源码) 包含内容:1.汽车模型展示;2.汽车肤;3.轮毂部件更;4.开关车门动画;5.汽车尺寸测量

    “线上购车3D全方位体验:汽车模型展示与个性化定制功能”,three.js案例- 线上购车3d展示(源码) 包含内容:1.汽车模型展示;2.汽车肤;3.轮毂部件更;4.开关车门动画;5.汽车尺寸测量;6.自动驾驶;7.镜面倒影;8.hdr运用;9.移动端适配; 本为html+css+three.js源码 ,核心关键词:three.js案例; 线上购车3D展示; 汽车模型展示; 汽车换肤; 轮毂部件更换; 开关车门动画; 汽车尺寸测量; 自动驾驶; 镜面倒影; HDR运用; 移动端适配; HTML+CSS+three.js源码。,"Three.js源码:线上购车3D展示案例,含汽车模型、换肤、轮毂更换等九大功能"

    (数据权威)中国城市_县域统计面板数据二合一

    数据名称:2000-2022年各县市区主要社会经济发展指标面板数据 数据类型:dta格式 数据来源:中国县域统计

    120页-环卫车项目初步方案.pdf

    一、智慧环卫管理平台的建设背景与目标 智慧环卫管理平台的建设源于对环卫管理全面升级的需求。当前,城管局已拥有139辆配备车载GPS系统、摄像头和油耗传感器的环卫车辆,但环卫人员尚未配备智能移动终端,公厕也缺乏信息化系统和智能终端设备。为了提升环卫作业效率、实现精细化管理并节省开支,智慧环卫管理平台应运而生。该平台旨在通过信息化技术和软硬件设备,如车载智能终端和环卫手机App,实时了解环卫人员、车辆的工作状态、信息和历史记录,使环卫作业管理透明化、精细化。同时,平台还期望通过数据模型搭建和数据研读,实现更合理的环卫动态资源配置,为环卫工作的科学、健康、持续发展提供决策支持。 二、智慧环卫管理平台的建设内容与功能 智慧环卫管理平台的建设内容包括运行机制体制建设、业务流程设计、智慧公厕系统建设、网络建设、主机和储存平台需求、平台运维管理体系、硬件标准规范体系以及考核评价体系等多个方面。其中,智慧公厕系统建设尤为关键,它能实时监控公厕运行状态,保障公厕的清洁和正常运行。平台建设还充分利用了现有的电子政务网络资源,并考虑了有线和无线网络的需求。在功能上,平台通过普查、整合等手段全面收集环卫车辆、企业、人员、设施、设备等数据,建立智慧环卫基础数据库。利用智能传感、卫星定位等技术实现环卫作业的在线监管和远程监控,实现对道路、公共场所等的作业状况和卫生状况的全面监管。此外,平台还建立了环卫作业网格化管理责任机制,实现从作业过程到结果的全面监管,科学评价区域、部门、单位和人员的作业效果。 三、智慧环卫管理平台的效益与风险规避 智慧环卫管理平台的建设将带来显著的环境、经济和管理效益。环境方面,它将有力推进环境卫生监管服务工作,改善环境卫生状况,为人民群众创造更加清洁、卫生的工作和生活环境。经济方面,通过智慧化监管,大大降低了传统管理手段的成本,提高了监管的准确性和效率。管理方面,平台能够追踪溯源市民反映的问题,如公厕异味、渣土车辆抛洒等,并找到相应的责任单位进行处置,防止类似事件再次发生。同时,平台还拥有强大的预警机制功能,能够在很多环卫问题尚未出现前进行处置。然而,平台建设也面临一定的风险,如部门协调、配合问题,建设单位选择风险以及不可预测的自然灾害等。为了规避这些风险,需要加强领导、统一思想,选择优秀的系统集成商承接项目建设,并做好计算机和应用系统的培训工作。同时,也要注意标准制定工作和相关法律法规的制定工作,以保证系统建设完成后能够真正为环卫管理工作带来便利。

    36 -企业管理主管绩效考核表1.xlsx

    36 -企业管理主管绩效考核表1

    1.1 -1.4 工程代码

    1.1 -1.4 工程代码

    USDT合约,USDT智能合约

    USDT合约,USDT智能合约

    基于姿态估计三维人脸形状重建.pdf

    基于姿态估计三维人脸形状重建.pdf

    一般员工绩效考核表模板(通用版) (2).xls

    一般员工绩效考核表模板(通用版) (2)

    全国295个地级市2011-2022互联网宽带接入用户数互联网普及率(数据权威)

    全国各省295地级市互联网普及率、互联网用户数、每百人互联网宽带用户(2011-2022年) 数据年份:2011-2022年(2022存在部分缺失) 数据范围:全国各省295个地级市 数据来源:地方统计局

    (数据权威)碳排放、碳中和、碳交易、碳金融、碳计算、碳建模资料

    一、各省、分行业CO2排放、283个地级市碳排放及计算过程 2.分行业二氧化碳排放量 在这里插入图片描述 3、280多个地级市碳排放及计算过程 二、碳中和文献、最新政策、碳金融数据+数学建模 1.二氧化碳减排规划,碳金融数据收集及数学建模 2.碳中和政策和下载量最高的碳中和论文 三、碳排放+碳市场+碳交易+碳中和+碳排放核算Excel自动计算表 全行业碳排放核算Excel自动计算表 四、碳交易数据 五、主要能源碳排放计算参数

    第20讲:自定义类型:结构体.pdf

    第20讲:自定义类型:结构体

    视觉跟踪算法综述.pdf

    视觉跟踪算法综述.pdf

    MATLAB超效率SBM-DEA模型代码详解:简易操作指南及期望与非期望产出的超效率分析,附Malmquist指数与分解功能,MATLAB的超效率SBM-DEA模型代码(有安装教程和内容讲解之类的东西

    MATLAB超效率SBM-DEA模型代码详解:简易操作指南及期望与非期望产出的超效率分析,附Malmquist指数与分解功能,MATLAB的超效率SBM-DEA模型代码(有安装教程和内容讲解之类的东西),操作很简单 可以做期望产出和非期望产出的超效率和非超效率sbm模型和Malmquist指数和分解 ,MATLAB; SBM-DEA模型; 超效率SBM-DEA; 安装教程; 内容讲解; 期望产出; 非期望产出; 超效率与非超效率sbm模型; Malmquist指数; 分解。,"MATLAB超效SBM-DEA模型代码:非期望产出分析的便捷工具"

    人事行政主管绩效考核评分表.xls

    人事行政主管绩效考核评分表

Global site tag (gtag.js) - Google Analytics