c++

方法1: 计算两次子序列
考虑拦截导弹的序列(下降序列)的结尾值,这些结尾值构成了上升子序列, 如果要拦截全部导弹, 那么需要考虑一个$\min\max$问题, 即最长上升子序列

#include <bits/stdc++.h>

using namespace std;

int main(){
    vector<int> missiles;
    int mis;
    while(cin>>mis) missiles.push_back(mis);

    int N = missiles.size();
    int f[N];
    memset(f, 0x00, sizeof f);
    // 计算导弹的最长下降子序列的长度
    int maxN = 1;
    for(int i=0; i<N; ++i){
        f[i]=1;
        for(int j=0; j<i; ++j){
            if(missiles[i]<=missiles[j])
                f[i]=max(f[i], f[j]+1);
        }
        maxN = max(maxN, f[i]);
    }

    cout<<maxN<<endl;
    // 计算需要拦截所有导弹需要的系统数量
    // 计算最长上升子序列方法
    maxN = 1;
    for(int i=0; i<N; ++i){
        f[i]=1;
        for(int j=0; j<i; ++j){
            if(missiles[i]>missiles[j])
                f[i]=max(f[i], f[j]+1);
        }
        maxN = max(maxN, f[i]);
    }
    cout<<maxN<<endl;

    return 0;
}

方法2: 贪心

#include <bits/stdc++.h>

using namespace std;

int main(){
    vector<int> missiles;
    int mis;
    while(cin>>mis) missiles.push_back(mis);

    int N = missiles.size();
    int f[N];
    memset(f, 0x00, sizeof f);
    // 计算导弹的最长下降子序列的长度
    int maxN = 1;
    for(int i=0; i<N; ++i){
        f[i]=1;
        for(int j=0; j<i; ++j){
            if(missiles[i]<=missiles[j])
                f[i]=max(f[i], f[j]+1);
        }
        maxN = max(maxN, f[i]);
    }

    cout<<maxN<<endl;
    // 计算需要拦截所有导弹需要的系统数量
    // 贪心算法
    // 将导弹加入到下降子序列最小末位置大于当前值的序列
    int g[N];
    memset(g, 0x00, sizeof g);
    int cnt=0;
    for(int i=0; i<N; ++i){
        int k=0;
        while(k<cnt && g[k]<missiles[i]) ++k;
        g[k]=missiles[i];
        if(k>=cnt) ++cnt;
    }

    cout<<cnt<<endl;

    return 0;
}

二分法优化单调数组查找

#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int a[N];
int f[N];

int main(){
    memset(a, 0x00, sizeof a);
    memset(f, 0x00, sizeof f);
    int n=1;
    while(cin>>a[n]) ++n;
    --n;

    // Q1
    int res=0;
    for(int i=1; i<=n; ++i){
        f[i]=1;
        for(int j=1; j<i; ++j){
            if(a[j]>=a[i]) f[i]=max(f[i], f[j]+1);
        }
        res=max(res, f[i]);
    }
    cout<<res<<endl;
    // Q2
    // res=0; // 初始状态, 建立0套防御系统
    // memset(f, 0x00, sizeof f); // 存储当前已经分配的子序列的结尾值, 单调上升的数组
    // for(int i=1; i<=n; ++i){
    //     int k=1;
    //     while(k<=res && f[k]<a[i]) ++k; // 尝试在当前下降序列中找到结尾值恰好大于a[i]的序列
    //     f[k]=a[i]; // 更新序列结尾值
    //     if(k>res) ++res; // 需要新系统
    // }
    // cout<<res<<endl;

    // Q2使用二分法优化
    res=0; // 表示单调数组的长度
    memset(f, 0x00, sizeof f);
    for(int i=1; i<=n; ++i){
        if(!res || f[res-1]<a[i]) f[res++]=a[i];
        else{
            int l=0, r=res-1;
            while(l<r){
                int mid=l+(r-l)/2;
                if(f[mid]<a[i]) l=mid+1;
                else r=mid;
            }
            f[l]=a[i];
        }
    }
    cout<<res<<endl;

    return 0;
}

python

from typing import List
class Solution:
    def main(self, n:int, a:List[int]):
        res, f=0, [1 for _ in range(n)]
        for i in range(n):
            for j in range(i):
                if a[j]>=a[i]:
                    f[i]=max(f[i], f[j]+1)
            res=max(res, f[i])
        print(res, end='\n')

        f, res=[], 0
        for i in range(n):
            if not f or f[res-1]<a[i]: 
                f.append(a[i])
                res+=1
            else:
                l, r=0, res-1
                while l<r:
                    mid = l+(r-l)//2
                    if f[mid]<a[i]: l=mid+1
                    else: r=mid
                f[l]=a[i]
        print(res, end='\n')


if __name__=='__main__':
    a=list(map(int, input().split()))
    n=len(a)
    sol=Solution()
    sol.main(n, a)