程序员的好印象（最长不下降子序列）

╰+哭是因爲堅強的太久メ 2023-01-16 02:38 154阅读 0赞

https://ac.nowcoder.com/acm/problem/15759

最长不下降子序列的模板，直接食用。

下面重点理解核心代码：

b[i] = 1; // 每次先把自己算进来，自己的个数，当然是1

for(int j = 1; j < i; j++)
                if(a[j] <= a[i]) b[i]=max(b[i], b[j]+1);  
    （1）j < i, 算过自己，就不要再算了，依次看看之前有几个比我小
    （2）b[i]=max(b[i], b[j]+1) 如果 之前有一个数(a[j])比我小，比你小的个数(b[j])加1（加上自身）和自身取最大
    （3）cnt = max(b[i], cnt) 每次取最大的数

ac代码

#include<bits/stdc++.h>
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    using namespace std;
    
    int a[105], b[105];
    
    void sovle()
    { 
        int n;
        while(cin>>n&&(n!=0))
        { 
            rep(i,1,n) cin >> a[i];
            int cnt = 0;
            rep(i,1,n)
            { 
                b[i] = 1;  // reset
            
    
    for(int j = 1; j < i; j++){ 
                if(a[j] <= a[i]) b[i]=max(b[i], b[j]+1);  // 如果之前的数小于这个数，添加进来
            }
                cnt = max(b[i], cnt);
            }
            cout << cnt <<endl;
            
        }
    }
    
    int main()
    { 
        ios;
        sovle();
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关计蒜客最长不下降子序列（nlogn算法）

求最长不下降子序列的长度第一行为n，表示n个数第二行n个数最长不下降子序列的长度 N小于5000for each num < =maxint 样例输入

红太狼/ 2024年02月17日 22:18/ 0 赞/ 44 阅读

相关程序员的好印象（最长不下降子序列）

https://ac.nowcoder.com/acm/problem/15759 最长不下降子序列的模板，直接食用。下面重点理解核心代码： b[i] = 1;

╰+哭是因爲堅強的太久メ/ 2023年01月16日 02:38/ 0 赞/ 155 阅读

相关 LIS 模板 (最长上升/下降子序列) STL实现

群里分享的模板，O(nlogn)，真心精简…… 最近接触了函数 count\_if 也一起记录进去了。修改自：http://paste.ubuntu.com/623003

短命女/ 2022年09月17日 11:14/ 0 赞/ 197 阅读

相关最长不下降自序列（最长递增子序列）C++动态规划

题目：[http://www.kencoding.net/problem.php?id=1112][http_www.kencoding.net_problem.php_id_

你的名字/ 2022年08月29日 15:52/ 0 赞/ 183 阅读

相关最长不下降子序列

Problem B: So easy Time Limit: 2 Sec Memory Limit: 128 MB Submit: 34 Solved: 11

忘是亡心i/ 2022年07月15日 10:17/ 0 赞/ 162 阅读

相关最长不下降子序列

/开辟一个堆栈数组stack[]，每次取栈顶元素top和读到的元素temp做比较，如果temp>top则将temp入栈，如果temp<=top则二分查找栈中的

绝地灬酷狼/ 2022年06月16日 13:45/ 0 赞/ 211 阅读

相关 HDU 6197 array array array(最长不下降子序列)

array array array Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

桃扇骨/ 2022年06月08日 01:17/ 0 赞/ 178 阅读

相关最长上升子序列，最长不下降子序列

最长上升子序列 include<iostream> include<cstdio> using namespace std; const in

深藏阁楼爱情的钟/ 2022年05月13日 22:55/ 0 赞/ 279 阅读

相关最长不下降子序列

定义：设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 例如3，18，7，14，10，12，23，41，1

悠悠/ 2022年04月15日 05:42/ 0 赞/ 186 阅读

相关最长不下降子序列自实现

在学习动态规划过程中,下面是我自己实现的LIS,时间复杂度O(n),不知道正确与否,先记下来 include <iostream> include <algo

水深无声/ 2022年03月19日 08:08/ 0 赞/ 225 阅读