题解 | 拦截导弹

/*
ans1为最长递减子序列的长度
根据Dilworth定理:ans2为最少的下降序列个数就等于整个序列最长上升子序列的长度
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int a[N],dp[N],dp2[N],n;

int main(){
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];

    int ans1 = 0,ans2 = 0;
    for(int i = 1;i<=n;i++){
        dp[i] = dp2[i] = 1;
        for(int j = i-1;j>=1;j--){
            if(a[j]>=a[i]) dp[i] = max(dp[i],dp[j]+1);
            else dp2[i] = max(dp2[i],dp2[j]+1);
        }
        ans1 = max(ans1,dp[i]);
        ans2 = max(ans2,dp2[i]);
    }

    cout<<ans1<<"\n"<<ans2<<"\n";

    return 0;
}

#牛客春招刷题训练营#https://www.nowcoder.com/discuss/727521113110073344