最长不上升子序列的优化（nlogn）

港控/mmm° 2022-09-30 06:29 147阅读 0赞

一般的DP写法：

for (int i=1;i<=t;i++)
            {
                f[i]=1;
                for (int j=1;j<i;j++)
                if (num[i]>num[j]&&f[j]+1>f[i])
                    f[i]=f[j]+1;
            }
        int max=0;
        for (int i=1;i<=t;i++)if (f[i]>max) max=f[i];

看到[http://www.cnblogs.com/itlqs/p/5743114.html][http_www.cnblogs.com_itlqs_p_5743114.html]有个简洁的nlogn写法 学习一下.

#include<cstdio>
    #include<algorithm>
    using namespace std;
    
    int a[40005];
    int d[40005];
    
    int main()
    {
        int n;
        scanf("%d",&n);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        if (n==0)  //0个元素特判一下 
        {
            printf("0\n");
            return 0;
        }
        d[1]=a[1];  //初始化 
        int len=1;
        for (int i=2;i<=n;i++)
        {
            if (a[i]>=d[len]) d[++len]=a[i];  //如果可以接在len后面就接上 
            else  //否则就找一个最该替换的替换掉 
            {
                int j=upper_bound(d+1,d+len+1,a[i])-d;  //找到第一个大于它的d的下标 
                d[j]=a[i]; 
            }
        }
        printf("%d\n",len);    
        return 0;
    }

[http_www.cnblogs.com_itlqs_p_5743114.html]: http://www.cnblogs.com/itlqs/p/5743114.html

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1025 (最长上升子序列(nlogn)算法)

![尴尬][awkward.gif]本题真是各种WR都遇到了。。哎。不负苦心人题意：给一个n代表两边城市的个数，两边都有n个城市，城市编号不会重复，要求找最多能修多少路（

ゝ一世哀愁。/ 2024年02月17日 19:22/ 0 赞/ 81 阅读

相关最长上升子序列

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

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

相关最长不上升子序列的优化（nlogn）

一般的DP写法： for (int i=1;i<=t;i++) { f[i]=1;

港控/mmm°/ 2022年09月30日 06:29/ 0 赞/ 148 阅读

相关最长上升子序列nlogn算法

这题目是经典的DP题目，也可叫作LIS（Longest Increasing Subsequence）最长上升子序列或者最长不下降子序列。很基础的题目，有两种算法，复杂度分

╰半橙微兮°/ 2022年08月20日 04:15/ 0 赞/ 172 阅读

相关最长上升子序列O(nlogn)

模板： include <iostream> include <cstdio> using namespace std; const

秒速五厘米/ 2022年08月17日 14:23/ 0 赞/ 141 阅读

相关最长上升子序列

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 阅读

相关最长上升子序列

最长上升子序列 Time Limit: 3000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Probl

傷城~/ 2022年05月30日 10:09/ 0 赞/ 238 阅读

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

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

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

相关最长上升子序列 nlogn

最长上升子序列有dp的写法 f\[i\]:=max（f\[j\]）+1; f\[1\]:=1; ![ContractedBlock.gif][] ![ExpandedBl

迈不过友情╰/ 2022年01月07日 09:39/ 0 赞/ 207 阅读