nyoj--814--又见拦截导弹

不念不忘少年蓝@ 2022-06-10 06:55 136阅读 0赞

## 又见拦截导弹 ##

时间限制： 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

解题思路;

说是dp题，我感觉更像是一道贪心题，对第一发导弹是肯定需要用一个系统拦截的，从第二发导弹到最后一发，每当导弹发射过来的时候，就从已经启用的拦截系统，按照拦截的高度递增的顺序遍历，如果有可以拦截高度大于或者等于这个导弹的系统 就不用启动新的拦截系统，直接用已经启动的系统进行拦截，并更新这个系统拦截的高度。如果遍历已经开启的系统，发现没有能够拦截的。就只能开启新的导弹拦截系统了，同样需要存储该导弹能够拦截导弹的高度。

详见代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;n; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(scanf( 
 "%d",&nbsp;&amp;n)) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(n&nbsp;==&nbsp;- 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 break; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;a[ 
 3009]&nbsp;=&nbsp;{ 
 0};&nbsp; 
 ///每个导弹拦截系统可以拦截的最高高度，是一个递减的序列 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;k&nbsp;=&nbsp; 
 1,&nbsp;num,&nbsp;i; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(n--) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;num); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for(&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;&nbsp;k;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///因为a数组存储的导弹拦截的高度本来就是递增的，所以直接从1开始遍历即可 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(a[i]&nbsp;&gt;=&nbsp;num)&nbsp; 
 ///如果之前的导弹拦截系统能够拦住的话，就用之前的 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[i]&nbsp;=&nbsp;num;&nbsp; 
 ///并把该导弹拦截系统的拦截的最大高度刷新 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 break; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(i&nbsp;==&nbsp;k)&nbsp; 
 ///否则的话就要新增加一个导弹拦截系统 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[k++]&nbsp;=&nbsp;num; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n",&nbsp;k&nbsp;-&nbsp; 
 1); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>