题解 | #拦截导弹#

解题思路：

• 入坑思路，求得最长不严格下降子序列以后，思路一直在记录经历过的点上，思索良久发现不可行。最后查看dp数组中的值，想发现一些规律，迷惑地发现，只要在dp数组中求出严格上升子序列的个数就可以获得答案，结果过了5个测试点后挂了。接下来没有任何思路了。
• 通过看题解知道了一个牛逼的Dilworth定理。然后按部就班地套一发就过了。

#include<bits/stdc++.h>
using namespace std;
//求得最长下降子序列长度完成第一问，着实简单
int solve(int i, vector<int> &v, vector<int> &dp){
    if(dp[i] != 0) return dp[i];
    if(i == 0) {
        dp[i] = 1;
    }
    else{
         int mx = 0;
         for(int j = 0; j < i; ++j){
             int tmp = solve(j, v, dp);
             if(v[i] <= v[j]) mx = max(tmp, mx);
         }
         dp[i] = mx+1;
    }
    return dp[i];
}
//求得最长严格上升子序列的长度，也很简单。
int up_solve(int i, vector<int>&v, vector<int>&dp2){
    if(dp2[i] != 0) return dp2[i];
    if(i == 0){
        dp2[i] = 1;
    }
    else{
        int mx = 0;
        for(int j = 0; j < i; ++j){
            int tmp = up_solve(j, v, dp2);
            if(v[i] > v[j]) mx = max(tmp, mx);
        }
        dp2[i] = mx+1;
    }
    return dp2[i];
}
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    vector<int> dp(n);
    vector<int> dp2(n);
    for(int i = 0; i < n; ++i){
        cin>>v[i];
    }
    solve(n-1, v, dp);
    up_solve(n-1, v, dp2);
    int ans1 = 0, ans2 = 0;
    for(auto i : dp){
        ans1 = max(ans1,i);
    }
    for(auto j: dp2){
        ans2 = max(ans2, j);
    }
    cout<<ans1<<endl;
    cout<<ans2<<endl;
    return 0;
}