【基础练习】【二分】codevs3955 最长严格上升子序列(加强版)题解

短命女 2022-08-09 05:22 163阅读 0赞

题目描述 Description

给一个数组a1, a2 ... an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。

输出长度即可。

输入描述 Input Description

第一行，一个整数N。

第二行 ，N个整数（N < = 1000000）

输出描述 Output Description

输出K的极大值，即最长不下降子序列的长度

样例输入 Sample Input

5

9 3 6 2 7

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

n<=1000000

为了方便大家调试，数据名称已被修改——THREE

所以，这道题目和上面的品尝美食是一样的= =只不过是严格上升而已

直接上代码

//codevs3955 最长严格上升子序列(加强版) 二分 
    //copyright by ametake 
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    const int maxn=1000000+10;
    int n,a[maxn];
    int f[maxn];
    int p;
    
    int find(int x)//目标：找出当前序列中比x大的第一个数的位置 
    {
        int l=1,r=p;
        while (l
           
            =x) r=mid; else l=mid+1; } return l; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); } p=1;//pointer f[1]=a[1]; for (int i=2;i<=n;i++) { if (a[i]>f[p]) { f[++p]=a[i]; } else { int pos=find(a[i]); f[pos]=a[i]; } } printf("%d",p); return 0; }

——衣带渐宽终不悔，为伊消得人憔悴

发表评论取消回复

表情：

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

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

相关阅读

相关 codevs1576 最长严格上升子序列动态规划dp

include<iostream> include<cstdio> using namespace std; int main(){

偏执的太偏执、/ 2024年02月17日 19:26/ 0 赞/ 38 阅读

相关最长上升子序列

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

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

相关最长上升子序列 II——题解

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数 N。第二行包含 N 个整数，表示完整序列。输出格式输出

╰半橙微兮°/ 2022年08月28日 12:59/ 0 赞/ 155 阅读

相关【基础练习】【二分】codevs2188 最长上升子序列(限定元素)题解

题目描述 Description LIS问题是最经典的动态规划基础问题之一。如果要求一个满足一定条件的最长上升子序列，你还能解决吗？给出一个长度为N整数序列，请求

浅浅的花香味﹌/ 2022年08月09日 05:24/ 0 赞/ 187 阅读

相关【基础练习】【二分】codevs3955 最长严格上升子序列(加强版)题解

题目描述 Description 给一个数组a1, a2 ... an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。输出长度即可。

短命女/ 2022年08月09日 05:22/ 0 赞/ 164 阅读

相关【基础练习】【线性DP】codevs1408 最长公共子序列（上升）题解

这道题目捣鼓了一个小时了终于弄出来咯···怒吼三声：容易吗！文章被盗还是很严重，加版权信息转载请注明出处 \[[ametake][]版权所有\][http://blog.csd

「爱情、让人受尽委屈。」/ 2022年08月02日 06:02/ 0 赞/ 199 阅读

相关【基础练习】【线性DP】codevs1576 最长严格上升子序列题解

连题目都不放了，就是标题中说的那样，裸题于是直接上代码 //codevs1576 最长严格上升子序列线性DP //copyright by ameta

刺骨的言语ヽ痛彻心扉/ 2022年08月01日 15:50/ 0 赞/ 163 阅读

相关最长上升子序列

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

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

相关最长上升子序列

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

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

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

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

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