AcWing 1012. 友好城市 (搞心态 + 最长上升子序列)

浅浅的花香味﹌ 2022-09-13 13:23 101阅读 0赞

最开始求 a 数组的时候，太搞人心态了

细想，细想

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    
    using namespace std;
    
    const int N = 5e3 + 100;
    
    int a[N],c[N],f[N];
    
    struct Node{ 
        int x, y;
        bool operator < (const Node &A) const 
        { 
            return x < A.x;
        }
    }b[N];
    
    int main()
    { 
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) 
        { 
            cin >> b[i].x >> b[i].y;
            c[i] = b[i].y;
        }
        
        sort(b, b+n);
        
        sort(c, c+n);
        
        for(int i = 0; i < n; i++)
            a[i] = lower_bound(c,c+n,b[i].y)-c;
      
        
        
        int ans = 1;
        
        for(int i = 0; i < n; i++)
        { 
            f[i] = 1;
            for(int j = i; j >= 0; j--)
            { 
                if(a[i] > a[j]) f[i] = max(f[i], f[j]+1);
            }
        }
        
        for(int i = 0; i < n; i++) ans = max(ans, f[i]);
        
        cout << ans;
        
    }

发表评论取消回复

表情：

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

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

相关阅读

相关最长上升子序列模型 AcWing 272. 最长公共上升子序列

最长上升子序列模型 AcWing 272. 最长公共上升子序列原题链接 [AcWing 272. 最长公共上升子序列][AcWing 272.] 算法标签

缺乏、安全感/ 2023年09月28日 14:26/ 0 赞/ 56 阅读

相关最长上升子序列模型 AcWing 1016. 最大上升子序列和

最长上升子序列模型 AcWing 1016. 最大上升子序列和原题链接 [AcWing 1016. 最大上升子序列和][AcWing 1016.] 算法标签

绝地灬酷狼/ 2023年09月28日 14:03/ 0 赞/ 134 阅读

相关线性DP AcWing 895. 最长上升子序列

线性DP AcWing 895. 最长上升子序列原题链接 [AcWing 895. 最长上升子序列][AcWing 895.] 算法标签动态规划线性D

分手后的思念是犯贱/ 2023年09月28日 12:56/ 0 赞/ 127 阅读

相关最长上升子序列

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

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

相关 AcWing 1012. 友好城市 (搞心态 + 最长上升子序列)

最开始求 a 数组的时候，太搞人心态了细想，细想 include <iostream> include <cstring> include <al

浅浅的花香味﹌/ 2022年09月13日 13:23/ 0 赞/ 102 阅读

相关 AcWing 1014. 登山 (最长上升子序列 + 思维)

最长上升子序列分为三种情况去讨论 include <iostream> include <cstring> include <algorithm>

ゝ一纸荒年。/ 2022年09月13日 13:21/ 0 赞/ 39 阅读

相关 1012 友好城市（转化-最长上升子序列问题）

1. 问题描述： Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相

ゝ一纸荒年。/ 2022年09月11日 13:12/ 0 赞/ 259 阅读

相关最长上升子序列

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

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

相关最长上升子序列

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

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

相关最长上升子序列

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

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