本文出自 http://blog.csdn.net/shuangde800
------------------------------------------------------------------------------------------------
题意
艾琳是个开火车的机师,她也负责车厢的调度。她喜欢把车厢依重量由大到小排列,把最重的车厢摆在火车的前方。
不幸的是,排列车厢并不容易。你不能直接把一截车厢拿起来放在别处。把一截车箱插入现有的列车中间并不切实际。一截车厢仅能接在列车的前面或后面。
车厢以事先排定的顺序抵达车站。当一截车厢抵达时,艾琳可以把它接在列车的前方或后方,或根本不要这截车厢。列车越长越好,但是其中的车厢要依重量排列。
依车厢抵达的顺序给你车厢的重量,艾琳所能接出的最长火车是多长?
思路
这题算是经典的类型题吧,看到这样的就应该想到LIS。
假设第一个车厢选择第i个放进去,那么接下来,放在i的右边的一定是比i的重量小的,为了让右边方向尽量长,
就要在序列中第i个到最后一个选最长递减序列的顺序放。
要放在i的左边的,一定是比i的重量要大的,同理,为了让左边方向尽量长,应该找以i为第一个(不能让其他代替)的最长递增
序列。
如果用枚举第一个车厢的朴素的方法算,并用nlogn的算法求最长递增(减)序列,那么复杂度达到n*n*logn
而n最大2000, 计算量达到2000*2000*11 = 4000W+,显然超时。
所以需要转换一下,只需要逆序计算最长递增(减)序列,对于第i个,当它插入LIS序列时,可以得到以它为开始的最长递增(减)
序列的长度,等于在LIS序列第一个到插入位置的个数,就是他的最长递增(减)序列的长度了
可能没讲清楚,代码好理解。
注意,求最长递减序列时,我把每个数字转化成了负数,这样就变成了求最长递增序列,做起来更方便。
代码
<script src="https://code.csdn.net/snippets/875.js" type="text/javascript"></script>
分享到:
相关推荐
迈瑞生化仪bs-330与lis接口开发说明文档
STM32例程Tutorial 27 - Motion 3-Axis Accelerometer LIS3DSH.7z
东芝TBA-120FR生化仪连接LIS的官方说明书,非常的详细!
stm32L0单片机通过iic通讯控制LIS3DH三轴传感器,通过fifo模式读取数据
XFA6100A型血液细胞分析仪-普朗医疗 LIS通信数据2.zip XFA6100A型血液细胞分析仪,LIS接口,数据格式说明等
LIS3DSH是一款由意法半导体(STMicroelectronics)生产的超低功耗、高性能的三轴线性加速度传感器。它属于“nano”系列,并且带有嵌入式状态机,能够实现自主应用的编程。以下是LIS3DSH的一些主要特性和应用场景: ...
日立HITACHI-7180全自动生化仪LIS通讯协议
lidar数据las格式的详细说明(英文).方便了解las格式的具体内容.
Introduction ............................................................................................................................................1-1 Principles of Operation.......................
智慧数字化医疗——HIS EMR LIS PACS整体解决方案,共66页。 打破信息孤岛、数据独立现状,实现共享 以财务为中心过渡到以临床服务为中心的信息化建设 解决医院看病难,就诊流程复杂 ,方便患者,数据跟着患者走 ...
TOSHIBA TBA 2000FR 东芝 生化 LIS双向资料 doc TOSHIBA TBA 2000FR 东芝 生化 LIS双向资料 doc
检验仪器与信息系统的权威标准,200美刀买的,CLSI标准LIS-A1分析仪器与信息系统底层接口规范:Standard Specification for Low-Level Protocol to Transfer Messages Between Clinical Laboratory Instruments and...
人工智能-项目实践-python-python lis列表排序,按字符串长度从小到大排序 python lis列表排序,按字符串长度从大到小排序
KT-6610 LIS系统接口通讯协议说明书(V1.0.01)
迈瑞 BC-5800 LIS 通讯协议 全自动血液细胞分析仪通讯协议
Sophia-Flaum:LIS 351 2021Spring
LIS-------------------------临床检验信息系统LIS工作流程
资源分类:Python库 所属语言:Python 资源全名:adafruit-circuitpython-lis2mdl-2.1.8.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
adobe-fonts-revealer::fleur-de-lis:将Adobe Fonts(OTF)复制到您的下载目录
迈瑞BS系列 LIS协议接口