🏆今日学习目标：
🍀学会导弹拦截题目
✅创作者：贤鱼

题目

描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是==以后每一发炮弹都不能高于前一发的高度（可以等于）==。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹。
输入
第一行是一个整数 N（1<=N<=15），表示导弹数。
第二行包含 N 个整数，为导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）。
输出
一个整数，表示最多能拦截的导弹数。
样例输入
8
389 207 155 300 299 170 158 65
样例输出
6

思路

很明显,这就是一个求最长不下降子序列的题,这里用nlogn的方法讲解题目
首先了解一下lower_bound和upper_bound()

来看一下如何求不下降子序列
这里的n储存了所有导弹的高度,r1从1开始,将第一个导弹的高度贤赋值,所以r1就是最长不上升子序列的长度

==389 207 155 300 299 170 158 65==用题解举个例子来看看下列代码
==389 207 155==会都加进去
==到了300的时候==,会进入else,这里*指的是地址,而这一句话的意思就是将第一个小于等于这个高度,于是数组变成了==389 300 155==
到==299==的时候会替换掉==155==,于是数组变成了==389 300 299==
接下来的==170 159 65==都可以顺利加入,所以最后的答案是==6==

b1[1]=n[1];
    r1=1;
for(int i=2;i<=c;i++){
        if(b1[r1]>=n[i]){
            b1[++r1]=n[i];
        }
        else {
            *upper_bound(b1+1,b1+r1+1,n[i],greater<int>())=n[i];
        }
    }

代码

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int n[2002],t=1,f;
int b1[2002],b2[2002],r1,r2;
int main(){
    int c;
    cin>>c;
    for(int i=1;i<=c;i++){
        cin>>n[i];
    }
    b1[1]=n[1];
    r1=1;
    for(int i=2;i<=c;i++){
        if(b1[r1]>=n[i]){
            b1[++r1]=n[i];
        }
        else {
            *upper_bound(b1+1,b1+r1+1,n[i],greater<int>())=n[i];
        }
    }

    cout<<r1<<endl;
}

拓展

==有些题目还要求说至少多少个拦截装置可以拦截多少导弹,这里我们一起对其做出解答==

狄尔沃斯定理(Dilworth 定理)

这里不对定理做出解答,如有需要可以看这里狄尔沃斯定理

总结一下:==其最长链中元素的数目必等于其最小反链划分中反链的数目==,只需要理解这句话,就可以发现题目没有任何难度

    b2[1]=n[1];
    r2=1;
    for(int i=2;i<=c;i++){
        if(b2[r2]<n[i]){
            b2[++r2]=n[i];
        }
        else {
            *lower_bound(b2+1,b2+r2+1,n[i])=n[i];
        }
    }

只要上面的定理理解了,这个题目就没有任何的难度了

==如果对您有需要,可以订阅一下专栏,持续更新哦==