导弹拦截（思路完整）

不要慌，我们先看题
双倍经验

---

---

---

---

---

---

---

拦截系统只能后一发高度<=前一发高度。一个导弹系统只能进行一次，那么就是找最长单调不升子序列。
不要觉得第一问有多个系统，第一问只是求一个

可以用dp？但是看到这里范围 **O($n^{2}$)**已经开心了吓哭了

所以我们需要换一种思路，既然是最长子序列，可以手动维护啊！

手动维护是用贪心+二分+实时更新序列维护，
那么ans1的数字就显而易见了

下面是第一问代码

f[0]=5e4+5;//因为当a[i]比当前尾项小，子序列答案就要增加长度，一开始a[1]一定是满足条件的
    for(int i=1;i<=n;i++){
        if(a[i]<=f[cnt]){
            cnt++;
            f[cnt]=a[i];//加长子序列
        }else{
            int l=1,r=cnt;
            while(l<r){
                int mid=(l+r)/2;
                if(f[mid]<a[i]){
                    r=mid;
                }else{     //二分，因为f数组始终单调不升
                    l=mid+1;
                }
            }
            f[l]=a[i];   //更新
        }
    }
    cout<<cnt;   //cnt代表序列长度

第二问
这里需要介绍一下高贵易懂的dilworth 定理
传送门开启知识，洛谷大牢仔细说，感谢大牢文章zc
”其最大反链中元素的数目必等于最小链划分中链的数目“这句话的意思是：将一个序列剖成若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数
因此，我们求一次最长上升子序列.

---

好了题解到此结束，附上参考代码

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int n;
int f[100004];
int cnt;
int main(){
    int x;
    while(cin>>x){
        n++;
        a[n]=x;
    }
    f[0]=5e4+5;
    for(int i=1;i<=n;i++){
        if(a[i]<=f[cnt]){
            cnt++;
            f[cnt]=a[i];
        }else{
            int l=1,r=cnt;
            while(l<r){
                int mid=(l+r)/2;
                if(f[mid]<a[i]){
                    r=mid;
                }else{
                    l=mid+1;
                }
            }
            f[l]=a[i];
        }
    }
    cout<<cnt;
    cnt=0;
    f[0]=-5e4-5;
    for(int i=1;i<=n;i++){
        if(a[i]>f[cnt]){
            cnt++;
            f[cnt]=a[i];
        }else{
            int l=1,r=cnt;
            while(l<r){
                int mid=(l+r)/2;
                if(f[mid]>=a[i]){
                    r=mid;
                }else{
                    l=mid+1;
                }
            }
            f[l]=a[i];
        }
    }
    cout<<endl<<cnt;
    return 0;
}

markdown编写不易，点个赞吧！