AcWing 1014. 登山 (最长上升子序列 + 思维)

ゝ一纸荒年。 2022-09-13 13:21 9阅读 0赞

最长上升子序列分为三种情况去讨论

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e3 + 100;
    
    int a[N], f[N], dp[N], ff[N];
    
    int main()
    { 
        int n, ans = 1;
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> a[i], f[i] = 1,dp[i]=1, ff[i] = 1;
        
        for (int i = 0; i < n; i++)
        { 
            for(int j = i; j >= 0; j--)
            { 
                if(a[i] < a[j]) dp[i] = max(dp[i], dp[j]+1); // 第一种是上升 
                if(a[i] > a[j]) f[i] = max(f[i], f[j]+1); // 第二种是下降
            }
        }
        for(int i = 0; i < n; i++) ans = max({ ans, f[i], dp[i]});
    
        // 还有一种是先上升，然后下降。
        
        for(int i = n-1; i >= 0; i--)
        { 
            for(int j = i; j < n; j++)
            { 
                if(a[i] > a[j]) ff[i] = max(ff[i], ff[j]+1);
            }
        }
        
        
        for(int i = 0; i < n; i++) 
        { 
            ans = max({ ans, f[i]+ff[i]-1});
        }
        
        cout << ans;
        
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划 | 线性dp | 最长上升子序列模型No.1】AcWing1017.怪盗基德的滑翔翼 & AcWing1014.登山

【算法|动态规划 | 线性dp | 最长上升子序列模型No.1】AcWing1017.怪盗基德的滑翔翼 & AcWing1014.登山 & AcWing 1012. 友好城市

刺骨的言语ヽ痛彻心扉/ 2024年04月27日 06:52/ 0 赞/ 54 阅读

相关最长上升子序列模型 AcWing 272. 最长公共上升子序列

最长上升子序列模型 AcWing 272. 最长公共上升子序列原题链接 [AcWing 272. 最长公共上升子序列][AcWing 272.] 算法标签

缺乏、安全感/ 2023年09月28日 14:26/ 0 赞/ 18 阅读

相关最长上升子序列模型 AcWing 1016. 最大上升子序列和

最长上升子序列模型 AcWing 1016. 最大上升子序列和原题链接 [AcWing 1016. 最大上升子序列和][AcWing 1016.] 算法标签

绝地灬酷狼/ 2023年09月28日 14:03/ 0 赞/ 109 阅读

相关线性DP AcWing 895. 最长上升子序列

线性DP AcWing 895. 最长上升子序列原题链接 [AcWing 895. 最长上升子序列][AcWing 895.] 算法标签动态规划线性D

分手后的思念是犯贱/ 2023年09月28日 12:56/ 0 赞/ 106 阅读

相关最长上升子序列

最长上升子序列 1、参考资料 https://leetcode-cn.com/problems/longest-increasing-subsequence/ h

- 日理万妓/ 2022年12月04日 07:57/ 0 赞/ 232 阅读

相关 AcWing 1014. 登山 (最长上升子序列 + 思维)

最长上升子序列分为三种情况去讨论 include <iostream> include <cstring> include <algorithm>

ゝ一纸荒年。/ 2022年09月13日 13:21/ 0 赞/ 10 阅读

相关 1014 登山（最长上升子序列扩展）

1. 问题描述：五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时

浅浅的花香味﹌/ 2022年09月11日 12:30/ 0 赞/ 158 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

港控/mmm°/ 2022年07月12日 02:47/ 0 赞/ 231 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

墨蓝/ 2022年07月12日 02:47/ 0 赞/ 255 阅读

相关最长上升子序列

严格上升和非严格上升的 include <iostream> using namespace std; int main() {

柔光的暖阳◎/ 2022年06月15日 09:52/ 0 赞/ 315 阅读