牛客网：拦截导弹

 这题通过一个数学定理将问题转化成了求最长递增子序列的问题。

首先，第一问很明显就是求最长非递减子序列，第二问要用一个定理，可以参考：

Dilworth定理是个啥东东_litble的博客-CSDN博客_dilworth定理

最后转化了问题后，求解就显得十分的简单，数学yyds，代码如下所示：

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

// 求最长非递减子序列长度
int solve1(vector<int> &height){
    int len=height.size();
    int res=INT_MIN;
    vector<int> dp(len, 1);
    for(int i=0;i<len;++i){
        for(int j=0;j<i;++j){
            if(height[i] <= height[j]){
                dp[i]=max(dp[i], dp[j]+1);
            }
        }
        res=max(res, dp[i]);
    }
    return res;
}

// 求最长递增子序列长度
int solve2(vector<int> &height){
    int len=height.size();
    int res=INT_MIN;
    vector<int> dp(len, 1);
    for(int i=0;i<len;++i){
        for(int j=0;j<i;++j){
            if(height[i] > height[j]){
                dp[i]=max(dp[i], dp[j]+1);
            }
        }
        res=max(res, dp[i]);
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    vector<int> height(n);
    for(int i=0;i<n;++i){
        cin>>height[i];
    }
    int res1=solve1(height);
    int res2=solve2(height);
    cout<<res1<<endl<<res2<<endl;
    return 0;
}