【LIS的nlogn做法】ABC134 E - Sequence Decomposing

今天药忘吃喽~ 2024-03-17 11:16 10阅读 0赞

[E - Sequence Decomposing (atcoder.jp)][E - Sequence Decomposing _atcoder.jp]

题意：

![508db591c5eb4b858af2996ab463217c.png][]

思路：

让你求一个序列里上升子序列个数

Dilworth定理告诉我们答案就是最长非上升子序列长度

那就是反着用nlogn求最长上升子序列长度

可以当板子用

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int Inf=1e18;
    
    int N;
    
    void solve(){
        cin>>N;
        vector<int> a(N,0),dp(N,Inf);
        for(int i=0;i<N;i++) cin>>a[i];
        reverse(a.begin(),a.end());
        for(int i=0;i<N;i++){
            *upper_bound(dp.begin(),dp.begin()+N,a[i])=a[i];
        }
        cout<<lower_bound(dp.begin(),dp.begin()+N,Inf)-dp.begin()<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[E - Sequence Decomposing _atcoder.jp]: https://atcoder.jp/contests/abc134/tasks/abc134_e
[508db591c5eb4b858af2996ab463217c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/59d41a49141943eebbc678c199b8bf36.png

发表评论取消回复

表情：

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

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

相关阅读

相关 Atcoder ABC 139E

Atcoder ABC 139E 题意: > n支球队大循环赛，每支队伍一天只能打一场，求最少几天能打完。解法： > 考虑抽象图论模型，既然一天只...

爱被打了一巴掌/ 2024年04月20日 10:31/ 0 赞/ 91 阅读

相关【BFS】ABC292 E - Transitivity

[E - Transitivity (atcoder.jp)][E - Transitivity _atcoder.jp] ![b00ee1dbbdc844359167433

小咪咪/ 2024年03月23日 14:43/ 0 赞/ 50 阅读

相关【状压DP/LIS】ABC237 F - |LIS| = 3

[F - |LIS| = 3 (atcoder.jp)][F - _LIS_ _ 3 _atcoder.jp] 感觉好帅尤其是jiaols的代码，怎么看都好帅题意：

阳光穿透心脏的1/2处/ 2024年03月23日 14:25/ 0 赞/ 61 阅读

相关 ABC247 E - Max Min

s b二分调 n m半天调不出来不写了，写不了一点直接贴别人代码算了题意： ![16d036c1f6324a3a9812f9a2fd2c4148.png][]

秒速五厘米/ 2024年03月23日 10:57/ 0 赞/ 79 阅读

相关【GCD+MST】ABC210 E

这道题告诉我们，一道题一定要去手摸样例，多造几个数据，然后找思路很多时候，题目看错了，码完发现思路错了，调半天调不出来，思路一直在旧框架打转，这些情况都是不去考察实际情况导

雨点打透心脏的1/2处/ 2024年03月17日 19:16/ 0 赞/ 81 阅读

相关【DP+博弈】ABC195 E

[E - Lucky 7 Battle (atcoder.jp)][E - Lucky 7 Battle _atcoder.jp] 题意： ![44faf1c04ab542

ゞ浴缸里的玫瑰/ 2024年03月17日 15:40/ 0 赞/ 51 阅读

相关【LIS的nlogn做法】ABC134 E - Sequence Decomposing

[E - Sequence Decomposing (atcoder.jp)][E - Sequence Decomposing _atcoder.jp] 题意： ![50

今天药忘吃喽~/ 2024年03月17日 11:16/ 0 赞/ 11 阅读

相关【数学】ABC 319 E

[E - Bus Stops][] 题意： ![f19239bed77b4ffda13a74736273c59e.png][] ![7d16c61674c24f709d8

朱雀/ 2024年03月04日 08:04/ 0 赞/ 110 阅读

相关 E - Sequence in the Pocket

传送门：[Sequence in the Pocket][] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_sha

浅浅的花香味﹌/ 2022年08月28日 04:55/ 0 赞/ 4 阅读

相关 AtCoder ABC 128E Roadwork

题目链接：[https://atcoder.jp/contests/abc128/tasks/abc128\_e][https_atcoder.jp_contests_abc1

末蓝、/ 2021年11月01日 06:18/ 0 赞/ 281 阅读