文档章节

求最长递增子序列的nlogn算法

 阿豪boy
发布于 2017/02/24 19:00
字数 365
阅读 15
收藏 0
点赞 0
评论 0

又见拦截导弹

http://acm.nyist.net/JudgeOnline/problem.php?pid=814

时间限制:3000 ms  |  内存限制:65535 KB

难度:3

输入

有多组测试数据。
每组数据先输入一个整数N(N≤3000),代表有N发导弹来袭。接下来有N个数,分别代表依次飞来的导弹的导弹的高度。当N=-1时表示输入结束。

输出

每组输出数据占一行,表示最少需要多少套拦截系统。

样例输入

8
389 207 155 300 299 170 158 65
5
265 156 123 76 26

样例输出

2
1

描述

大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度。突然有一天,雷达捕捉到敌国的导弹来袭。由于该系统存在缺陷,所以如果想把所有的导弹都拦截下来,就要多准备几套这样的导弹拦截系统。但是由于该系统成本太高,所以为了降低成本,请你计算一下最少需要多少套拦截系统。

 

http://blog.csdn.net/u013806814/article/details/38711125

http://blog.csdn.net/u013806814/article/details/38901121

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 884
码字总数 632762
作品 0
西安
最长递增子序列(LIS)求解

问题描述 最长递增子序列也称 “最长上升子序列”,简称LIS ( longest increasing subsequence)。设L=是n个不同的实数的序列,L的递增子序列是这样一个子序列Lis=,其中k1...

gfsfg8545 ⋅ 2014/05/13 ⋅ 0

最长递增序列

题目,给定数字序列A,求A中最长的递增序列。 O(n^2)算法思想: 即求以A[j]结尾的最长递增序列L[j] 就相当于求 在序列A中,以排在A[j]前的元素每个元素结尾的最长递增序列,加上A[j]后仍然为...

hgfgoodcreate ⋅ 2015/12/24 ⋅ 0

算法知识梳理(7) - 数组第四部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛 ⋅ 2017/12/12 ⋅ 0

Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer ⋅ 2017/12/20 ⋅ 0

Dilworth定理 的相关应用

讲的好的博客证明 总结一下:给定一个序列, (假定有重复数字, 没有重复的类似推导) 1:如果求每次在其中选出一个不下降子序列并将其删掉, 求删完整个序列所需要的选择子序列的次数 (相当于求...

anxdada ⋅ 03/29 ⋅ 0

哈理工oj 1116 解题报告 动态规划-依次输出最长公共子序列的位置

哈理工OJ 1116 选美大赛 http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1116 这道题目其实跟其他 2星 求最长递增子序列的题目没什么区别,但标记为2星半,总是...

oldpan ⋅ 2014/07/09 ⋅ 0

POJ 1836: Alignment

题目在此 解题思路:这题出得有点偏离实际,但是呢,编故事本来就是为了丰富题目的,不管它了。 这题的本质是:给定一个序列,去掉一些项使其成为先递增后递减的子序列,求去掉项的最小数目。...

Alexander_zhou ⋅ 2014/03/04 ⋅ 0

面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛 ⋅ 2017/12/22 ⋅ 0

【算法系列 四】 String

字符串循环左移(九度OJ1362),要求时间复杂度O(N),空间复杂度O(1) 这是一道基本的题目,简单说来就是三次翻转 比如:abcdef 左移两位 cdefab 过程: ab 翻转 ba cdef 翻转 fedc 将上面两个翻...

Hosee ⋅ 2016/04/18 ⋅ 0

编程之美2.16 数组中最长递增子序列的长度

改进的方法看的头大了却还是不清楚,哎。。。搞算法的苦啊,纠结啊。 编程之美这本书里面就有关于这道题的一些解法,求一个一位数组中的最长序列的长度。例如,在序列1,3,2中,最长递增序列...

吟啸_徐行 ⋅ 2013/03/19 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Spring表达式语言(SpEL)

1、SpEL引用 Spring EL在bean创建时执行其中的表达式。此外,所有的Spring表达式都可以通过XML或注解的方式实现。下面将使用Spring表达式语言(SpEL),注入字符串,整数,Bean到属性。 SpEL的...

霍淇滨 ⋅ 26分钟前 ⋅ 0

Gradle使用阿里云镜像

gradle 生命周期中有一个初始化( Initialization )的过程,这个过程运行在 build script 之前,我们可以在这个地方做一点系统全局的设置,如配置仓库地址。 你可以在以下几个位置实现仓库地址...

明MikeWoo ⋅ 34分钟前 ⋅ 0

appium+python3.6

1.安装jdk1.8(不知道为啥只识别1.8,1.10不识别,所以为了少折腾,迁就安装1.8) http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html 配置 JAVA_HOME:...

Kampfer ⋅ 53分钟前 ⋅ 0

详解Apache 日志分割教程

一、日志切割 安装cronolog CentOS 5.3中编译安装Apache日志默认是不切割的,需要用用工具Cronnolog进行日志切割。 1.下载及安装 wget http://cronolog.org/download/cronolog-1.6.2.tar.gz ...

dragon_tech ⋅ 55分钟前 ⋅ 0

Keepalived介绍

负载均衡器(Load Balancer, LB )是一组能够将IP数据流以负载均衡形式转发到多台物理服务器的集成软件。有硬件负载均衡器和软件负载均衡器之分,硬件负载均衡器主要是在访问网络和服务器之间...

寰宇01 ⋅ 55分钟前 ⋅ 0

java8-Collections and Streams

stream和集合的区别是什么? 1.在计算的时候处理不同, 2.every element should be computed in the memory and then to be part of collections stream Stream apis filter with a predica......

writeademo ⋅ 今天 ⋅ 0

Confluence 6 重新获得附件指南

每一个文件在恢复上传到 Confluence 的时候必须单独重命名,你可以通过下面说明的 3 个方法中选择一个进行操作: 选择 A - 通过文件名恢复附件 如果你知道你需要恢复的每一个文件名,尤其是你...

honeymose ⋅ 今天 ⋅ 0

【每天一个JQuery特效】根据状态确定是否滑入或滑出被选元素

主要效果: 本文主要采用slideToggle()方法实现以一行代码同时实现以展开或收缩的方式显示或隐藏被选元素。 主要代码如下: <!DOCTYPE html><html><head><meta charset="UTF-8">...

Rhymo-Wu ⋅ 今天 ⋅ 0

度量.net framework 迁移到.net core的工作量

把现有的.net framework程序迁移到.net core上,是一个非常复杂的工作,特别是一些API在两个平台上还不能同时支持。两个类库的差异性,通过人工很难识别全。好在微软的工程师们考虑到了我们顾...

李朝强 ⋅ 今天 ⋅ 0

请不要在“微服务”的狂热中迷失自我!

微服务在过去几年一直是一个非常热门的话题(附录1)。何为“微服务的疯狂”,举个例子: 众所周知,Netflix在DevOps上的表现非常棒。Netfix可以做微服务。因此:如果我做微服务,我也将非常...

harries ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部