题目描述

输入

输出

样例输入

样例输出

源代码

#include<stdio.h>
int n,a[1000];
int b[1000];
int top;
int find(int x)
{
    
    int l=0,r=top;
    int mid;
    while(r>=l)
    {
    
        mid=(l+r)/2;
        if(x>=b[mid])
        {
    
            l=mid+1;
        }
        else r=mid-1;
    }
    return l;
}
int main()
{
    
    while(~scanf("%d",&n))
    {
    
        for(int i=0;i<n;i++)
        {
    
            scanf("%d",&a[i]);
        }
        top=0;
        b[0]=a[n-1];
        for(int i=n-2;i>=0;i--)
        {
    
            if(a[i]>=b[top])
            {
    
                b[++top]=a[i];
            }
            else b[find(a[i])]=a[i];
         } 
         printf("%d\r\n",top+1);
    }
    return 0;
 } 

关于这题

This question actually asks for it form a monotonically decreasing sequence 中 How many can there be at most
（So some missiles can not be intercepted The goal is to find the optimal solution）
例如：389 207 155 300 299 1 10 65 结果为4
设立a b 两个数组
aThe array starts with the second-to-last number Then the third to last and fourth to last…
bThe first element of the array is a数组的最后一个数
如果a比b 大 Put this number inb数组下标加一 的位置
如果a比b 小 排序barray not0元素 放到合适的位置