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

短命女 2022-09-17 11:14 197阅读 0赞

群里分享的模板，O(nlogn)，真心精简……

最近接触了函数 count\_if 也一起记录进去了。

修改自：http://paste.ubuntu.com/6230037/

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<functional>
    using namespace std;
    
    const int N = 131072;
    
    int n = 7, a[N] = {0,0,1,1,0,0,2};
    
    template<class Cmp>
    int LIS (Cmp cmp)
    {
        static int m, end[N];
        m = 0;
        for (int i=0;i<n;i++)
        {
            int pos = lower_bound(end, end+m, a[i], cmp)-end;
            end[pos] = a[i], m += pos==m;
        }
        return m;
    }
    bool greater1(int value)
    {
        return value >=1;
    }
    
    int main ()
    {
        cout << LIS(less<int>()) << endl;         //严格上升
        cout << LIS(less_equal<int>()) << endl;   //非严格上升
        cout << LIS(greater<int>()) << endl;      //严格下降
        cout << LIS(greater_equal<int>()) << endl;//非严格下降
        cout << count_if(a,a+7,greater1) << endl; //计数
        //第二个参数为末尾元素的下一个位置
        return 0;
    }
    
    //OUT：
    //3 5 2 4 3

发表评论取消回复

表情：

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

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

相关阅读

相关死嗑最长上升子序列（LIS）

[【模板】LIS][LIS] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM

灰太狼/ 2022年11月21日 15:22/ 0 赞/ 158 阅读

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

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

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

相关最长上升子序列

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

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

相关最长上升子序列

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

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

相关最长上升子序列（LIS）算法

理解：该子序列中后一项都比前一项大，例如有序列2 7 1 5 6 4 3 8 9，则`最长上升子序列`为2 5 6 8 9。具体应用：用于确定一个代价最小的调整方案

本是古典何须时尚/ 2022年05月28日 01:46/ 0 赞/ 229 阅读

相关 (LIS)最长上升子序列-二分优化

最长上升子序列-二分优化 -------------------- LIS定义：一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这

- 日理万妓/ 2022年05月15日 04:55/ 0 赞/ 241 阅读

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

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

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

相关 LIS:最长上升子序列(3种方法)

最长上升子序列是我在计蒜客中的蓝桥杯模拟题中遇到的。当事看到题目自己想了想，和最长相同子序列差不多。然后自己写了两种解法，一种是采用递归式的方法（时间复杂度估计2

素颜马尾好姑娘i/ 2022年03月16日 01:52/ 0 赞/ 235 阅读

相关最长上升子序列(LIS)长度及其数量

例题51Nod-1376，一个经典问题，给出一个序列问该序列的LIS以及LIS的数量。这里我学习了两种解法，思路和代码都是参考这两位大佬的： [https://www.c

本是古典何须时尚/ 2021年10月26日 15:16/ 0 赞/ 387 阅读

相关动态规划-最长上升子序列LIS

文章目录问题描述一.简单推论（非0 n情况） 1.问题分析 2.状态转移方程 3.参考代码 4

￡神魔★判官ぃ/ 2021年09月07日 06:03/ 0 赞/ 421 阅读