题目名称	588. [NOIP 1999]拦截导弹
输入输出	`missile.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2011-08-18加入
开放分组	全部用户
提交状态
分类标签	NOIP/CSP 动态规划贪心 LIS
	分享题解

通过：624，提交：1537，通过率：40.6%
Sky_miner	100	0.000 s	0.00 MiB	C++
‎MistyEye	100	0.000 s	0.00 MiB	C++
LOSER	100	0.000 s	0.00 MiB	C++
牧殇	100	0.000 s	0.00 MiB	C++
YGOI_真神名曰驴蛋蛋	100	0.000 s	0.00 MiB	C++
YGOI_真神名曰驴蛋蛋	100	0.000 s	0.00 MiB	C++
浮生随想	100	0.000 s	0.00 MiB	C++
Hzoi_YJX	100	0.000 s	0.00 MiB	C++
Hzoi_Queuer	100	0.000 s	0.00 MiB	C++
NewBee	100	0.000 s	0.00 MiB	C++

本题关联比赛
防止浮躁的小练习v0.7

关于拦截导弹的近10条评论(全部评论)
#include<iostream> #include<cstdio> using namespace std; int main(void) { freopen("missile.in","r",stdin); freopen("missile.out","w",stdout); int b = 0;int a[1000][2]; cin>>b; for(int i = 1;i<b+1;i++) { cin>>a[i][1]; a[i][2]=1; } for(int i = 2;i<b+1;i++) { int l = 0; for(int j = 1;j<=i-1;j++) { if(a[j][1]>a[i][1]&&a[j][2]>0) { l=a[j][2]; } if(l>0) { a[i][2]=l+1; } } } int sum= 0; for(int i = 1;i<b+1;i++) { if(a[i][2]>sum) sum = a[i][2]; } cout<<sum<<endl<<1; } 2018NOIP必胜！ 2018-09-08 11:01 43楼
总算搞出了stl双logn的做法。。。洛谷上的数据比这要科学，这里没有重复的一开始第一问求下降子序列也对了。。。 Hyoi_0Koto 2017-09-06 15:59 42楼
回复 @kZime : 大佬第二问的dp想法果然比蒟蒻的贪心不知道高到哪里去了%%% Hyoi_0Koto 2017-09-06 10:01 41楼
坑人[b]的数据读入，cin.eof()在linux下多读了一个字符，导致读入的导弹数比实际的多1，不写n--评测机过不了，写了本地windows过不了实力演员阵容 2017-07-23 14:27 40楼
一道题竟然写了5周！身败名裂小字、小瓶子 2017-06-20 22:02 39楼
终于过了... 不得不吐槽一下弱弱的数据... fate1 2017-05-11 22:24 38楼
问题2的dp一直理解不了，然后，然后打了个模拟... Fisher. 2017-04-27 16:37 37楼
第一问：最长不上升子序；第二问：最长上升子序； kZime 2017-01-21 22:01 36楼
把最长上升子序列复制粘贴了两遍，改了下符号，就过了。。。。。。 Zwoi_只会打表抄代码的蒟蒻 2016-10-21 21:23 35楼
还是有点晕啊!! Go灬Fire 2016-10-10 08:20 34楼

588. [NOIP 1999]拦截导弹

★★☆ 输入文件：missile.in 输出文件：missile.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

某国为了防御敌国的导弹袭击，发明出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于$30000$的正整数），计算这套系统最多能拦截多少导弹，和如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【输入文件】

只有一行，有$n(1\leq n\leq 1000)$个整数，中间用一个空格隔开，表示$n$枚导弹的高度。

【输出文件】

有两行，每行一个数。

第一行的整数表示一套系统最多拦截的导弹数量。

第二行的整数表示拦截所有导弹最少要配备的导弹拦截系统数量。

【输入样例】

389 207 155 300 299 170 158 65

【输出样例】

6
2

【样例解释】

一套系统最多能拦截的导弹为:389 399 299 170 158 65。

可以定义$2$套系统：一套拦截389 207 155，另外一套拦截300 299 170 158 65，当然还有其它方案。