题意

• 有若干导弹，拦截系统只能拦高度降序的一组导弹，问一套系统最多拦截多少导弹，拦截全部导弹需要几套系统

思路

• 对于第一个问题，直接对整个序列跑一个最长递减子序列(LDS Longest-Decreasing-Subsequence)

• 对于第二个问题，正解是跑一个最长递增子序列(LIS)

• 对于第二个问题，证明如下

  记程度n

  首先，至少需要n套系统，是显然可以得到的

  需要证明的是，至多也只需要n套系统，由Dilworth定理可得，一个序列的最少不上升子序列数目就是其LDS长度

AC代码

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

int a[101010];
int f1[101010];
int f2[101010];
int main(){
    int cnt=1;
    while (cin >> a[cnt++]);
    for(int i=1;i<cnt;i++){
        for(int j=1;j<i;j++){
            if(a[i]<a[j]){
                f1[i]=max(f1[i],f1[j]+1);
            }
        }
    }
    for(int i=1;i<cnt;i++){
        for(int j=1;j<i;j++){
            if(a[i]>a[j]){
                f2[i]=max(f2[i],f2[j]+1);
            }
        }
    }
    int ans1=0,ans2=0;
    for(int i=1;i<cnt;i++){
        ans1=max(ans1,f1[i]); 
        ans2=max(ans2,f2[i]); 
    }
    cout << ans1 << endl << ans2 <<endl;
    return 0;
}