牛客竞赛NC16810 拦截导弹
传送门
题目描述
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于 的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入描述
行,若干个整数(个数 )。
输出描述
行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
示例1
输入
389 207 155 300 299 170 158 65
输出
6
2
分析
首先明确,当且仅当一颗炮弹的高度和导弹相等时,导弹可被拦截。
设第 颗导弹的高度为 。
由题意,能够用一套拦截的导弹,其高度构成一个不上升序列。因此,一套系统最多能拦截的数量是数组 中最长不上升子序列。
对于第二个问题,考虑每一套设备分管一段 中的独立的不上升子序列(各个子序列在 中的下标没有交集,所有子序列的并集为 ),由 定理,不上升子序列的最小划分数为 的最长上升子序列长度。
综上所述,题目要求输出 的最长不上升子序列长度和最长上升子序列长度。
代码
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 11D_Beyonder's Blog!