| 题目名称 | 690. 导弹系统 |
|---|---|
| 输入输出 | missilea.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-03-30加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：35， 提交：65， 通过率：53.85% | ||||
 dateri |
100 | 0.000 s | 0.00 MiB | C++ |
 LGLJ |
100 | 0.000 s | 0.00 MiB | C++ |
 奇诺 |
100 | 0.003 s | 0.29 MiB | C++ |
|
LGLJ |
100 | 0.003 s | 0.32 MiB | C++ |
 狂飙霹雳虎 |
100 | 0.003 s | 1.05 MiB | C++ |
 苜 |
100 | 0.004 s | 0.29 MiB | C++ |
|
苜 |
100 | 0.004 s | 0.31 MiB | C++ |
 kxxy |
100 | 0.004 s | 0.32 MiB | C++ |
 粘粘自喜 |
100 | 0.004 s | 0.33 MiB | C++ |
 秋水落叶 |
100 | 0.005 s | 0.28 MiB | C++ |
| 本题关联比赛 | |||
| 20120330 | |||
| 关于 导弹系统 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
提示：既然没给数据范围，那必然是不要数组的。。
dateri
2016-09-09 22:42
5楼
| ||||
|
只会O(n^2)DP的蒟蒻表示看不懂榜上一堆神奇的O(n)算法.....
| ||||
|
回复 @猹比 :
不是啊喂= =，偶数时的情况开始是初始化为0的，因为在开始选择的那一个是奇数= =  水中音
2014-10-30 15:10
3楼
| ||||
|
回复 @真呆菌dsb :
……ls那坟蛋骗窝QAQ！ | ||||
|
数据范围？
 钨铅
2013-04-13 16:36
1楼
| ||||
liu_runda【问题描述】
很久很久以前， A 国发明了一套导弹系统，用来击落来自敌国的导弹。这个系统只需发射一颗导弹就可以击落对方多颗导弹，只要这些导弹的高度能组成一个不下降序列。
但是最近科学家们发现这个导弹系统不够强大，于是他们又发明了另外一套导弹系统，新系统能以一发导弹击落敌方更多导弹。大体上说，这个系统可以由近及远地击落导弹，当系统启动后，它先选择一颗敌方导弹击落，然后再选择一颗比上一个高度低且较远的导弹击落，第三次击落的会比第二颗高且更远， … ，总之，所击落的第奇数颗导弹是比前一颗更高且远的，而所击落的第偶数颗导弹则是比前一颗更低且远的。
现在，给你一个序列，表示由近及远的敌方导弹高度，请找出这套新系统发射一颗导弹所能击落敌方导弹的最大数目。
但是最近科学家们发现这个导弹系统不够强大，于是他们又发明了另外一套导弹系统，新系统能以一发导弹击落敌方更多导弹。大体上说，这个系统可以由近及远地击落导弹，当系统启动后，它先选择一颗敌方导弹击落，然后再选择一颗比上一个高度低且较远的导弹击落，第三次击落的会比第二颗高且更远， … ，总之，所击落的第奇数颗导弹是比前一颗更高且远的，而所击落的第偶数颗导弹则是比前一颗更低且远的。
现在，给你一个序列，表示由近及远的敌方导弹高度，请找出这套新系统发射一颗导弹所能击落敌方导弹的最大数目。
【输入格式】
输入文件包含多个测试数据。
在每一个测试数据里，第一行是一个整数 n （ 0 输入文件以 n=0 表示结束。
在每一个测试数据里，第一行是一个整数 n （ 0
【输出格式】
对于每个测试数据，输出能击落导弹的最大数目。
【输入样例】
missile.in
4
5 3 2 4
3
1 1 1
0
5 3 2 4
3
1 1 1
0
missile.out
3
1
3
1