题解 | 拦截导弹

拦截导弹

https://www.nowcoder.com/practice/218f3db1f66d465bbf9578625aa90785

/*
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

全部评论

相关推荐

06-26 17:24
已编辑
宁波大学 golang
迷失西雅图:别给,纯kpi,别问我为什么知道
点赞 评论 收藏
分享
05-29 09:02
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务