OpenJudge

05:拦截导弹

总时间限制:
1000ms
内存限制:
65536kB
描述
某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹。拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹。
输入
输入有两行,
第一行,输入雷达捕捉到的敌国导弹的数量k(k<=25),
第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出,以空格分隔。
输出
输出只有一行,包含一个整数,表示最多能拦截多少枚导弹。
样例输入
8
300 207 155 300 299 170 158 65
样例输出
6
来源
医学部计算概论2006期末考试题

1、2图论中的遍历问题,也可用解答树分析递归遍历 数据结构类型书籍都有详细分析有关图论算法
3、10数字升序问题可用枚举加决策也可用回溯《算法竞赛经典入门》7.2中有详细介绍各种变种的数字排列
6、7是贪心算法的经典题型《算法的乐趣》中有对各个算法通俗易懂详细介绍的经典母题
8、用三种基础排序<插入排序,冒泡排序,选择排序>《数据结构》排序章节有三种算法复杂度的分析
5、最长递增子序列的变形题,递减形式可用NP<本次题型中都可用动态规划思想分析解决>《妙趣横生的算法C++》对动态规划有通俗的介绍的例题分析
八皇后问题可缩小为4皇后问题,可用递推,回溯等思想解决

全局题号
1947
添加于
2016-09-16
提交次数
24
尝试人数
11
通过人数
10