最少拦截系统

朴灿烈づ我的快乐病毒、 2022-07-12 04:09 148阅读 0赞

#### Problem Description ####

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.

怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

#### Input ####

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

#### Output ####

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

#### Example Input ####

8 389 207 155 300 299 170 158 65

#### Example Output ####

#### Hint ####

[hdoj1275][]

Author

题解：找最长的非连续上升子串

<table style="border-spacing:0px; border-collapse:collapse!important; margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
 <tbody style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
  <tr style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
   <td style="padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:top!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:3em!important; line-height:1.1em!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; min-height:inherit!important; color:rgb(175,175,175)!important; background:none!important"> <code style="color:rgb(199,37,78); font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px 0.3em 0px 0px!important; margin:0px!important; border:0px!important; outline:0px!important; text-align:right!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:2.7em!important; line-height:1.1em!important; min-height:inherit!important; display:block!important; background:none!important">06</code></td> 
   <td style="padding:0px 0px 0px 0.5em!important; margin:0px!important; border-width:0px 0px 0px 3px!important; border-left-style:solid!important; border-left-color:rgb(108,226,108)!important; outline:0px!important; float:none!important; vertical-align:top!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; min-height:inherit!important; background:none!important"> <code style="color:rgb(199,37,78); font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">&nbsp;&nbsp;&nbsp;&nbsp;</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; color:rgb(0,102,153)!important; font-weight:bold!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">while</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">(</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; color:rgb(255,20,147)!important; font-weight:bold!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">scanf</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">(</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; color:blue!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">"%d"</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">,&amp;n)!=EOF)</code></td> 
  </tr> 
 </tbody> 
</table>

<table style="border-spacing:0px; border-collapse:collapse!important; margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
 <tbody style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
  <tr style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
   <td style="padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:top!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:3em!important; line-height:1.1em!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; min-height:inherit!important; color:rgb(175,175,175)!important; background:none!important"> <code style="color:rgb(199,37,78); font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px 0.3em 0px 0px!important; margin:0px!important; border:0px!important; outline:0px!important; text-align:right!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:2.7em!important; line-height:1.1em!important; min-height:inherit!important; display:block!important; background:none!important">10</code></td> 
   <td style="padding:0px 0px 0px 0.5em!important; margin:0px!important; border-width:0px 0px 0px 3px!important; border-left-style:solid!important; border-left-color:rgb(108,226,108)!important; outline:0px!important; float:none!important; vertical-align:top!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; min-height:inherit!important; background:none!important"> <code style="color:rgb(199,37,78); font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; color:rgb(255,20,147)!important; font-weight:bold!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">scanf</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">(</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; color:blue!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">"%d"</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">,&amp;a[i]);</code></td> 
  </tr> 
 </tbody> 
</table>

<table style="border-spacing:0px; border-collapse:collapse!important; margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
 <tbody style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
  <tr style="margin:0px!important; padding:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-size:1em!important; min-height:inherit!important; background:none!important"> 
   <td style="padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:top!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:3em!important; line-height:1.1em!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; min-height:inherit!important; color:rgb(175,175,175)!important; background:none!important"> <code style="color:rgb(199,37,78); font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px 0.3em 0px 0px!important; margin:0px!important; border:0px!important; outline:0px!important; text-align:right!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:2.7em!important; line-height:1.1em!important; min-height:inherit!important; display:block!important; background:none!important">21</code></td> 
   <td style="padding:0px 0px 0px 0.5em!important; margin:0px!important; border-width:0px 0px 0px 3px!important; border-left-style:solid!important; border-left-color:rgb(108,226,108)!important; outline:0px!important; float:none!important; vertical-align:top!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; min-height:inherit!important; background:none!important"> <code style="color:rgb(199,37,78); font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; color:rgb(255,20,147)!important; font-weight:bold!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">printf</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">(</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; color:blue!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">"%d\n"</code><code style="font-family:Consolas,'Bitstream Vera Sans Mono','Courier New',Courier,monospace!important; font-size:1em!important; padding:0px!important; margin:0px!important; border:0px!important; outline:0px!important; float:none!important; vertical-align:baseline!important; position:static!important; left:auto!important; top:auto!important; right:auto!important; bottom:auto!important; height:auto!important; width:auto!important; line-height:1.1em!important; min-height:inherit!important; background:none!important">,max);</code></td> 
  </tr> 
 </tbody> 
</table>

[hdoj1275]: http://acm.hdu.edu.cn/showproblem.php?pid=1275