问题 A: 导弹拦截

时间限制: 1 Sec  内存限制: 128 MB

提交: 62  解决: 38

[][][]

题目描述

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

输入导弹一次飞来的高度（雷达给出的高度不大于30000的正整数）。计算这套系统最多能拦截多少导弹。

输入

n颗依次飞来的导弹高度，导弹颗数<=1000。

输出

一套系统最多拦截的导弹数。

样例输入

7 300 250 275 252 200 138 245

样例输出

5

 

这道题题目可能需要发一下，相同名字之类的题目太多，难以分清。

这道题没记错的话用一个最长不上升子序列，yyhs上可能O（n^2

）过不了，所以打一个二分即可。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           const int MAXN=1007;using namespace std;int n;int a[MAXN];int dp[MAXN],num=0;void mid_find(int x);int main(){    scanf("%d",&n);    for (int i=1;i<=n;i++)        scanf("%d",&a[i]);    num=1;    dp[1]=a[1];    for (int i=2;i<=n;i++)    {        mid_find(a[i]);        }        printf("%d",num);}void mid_find(int x){    int l=1,r=num,mid;    while (l
           
            >1; if (dp[mid]>=x) l=mid+1; else r=mid; } if (dp[l]>=x) { num++; dp[num]=x; } else dp[l]=x;}