建立友好城市有什么用_缔结友好城市

建立友好城市有什么用_缔结友好城市原题连接Palmia国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避免事故。编程帮助政府做出一些批准和拒绝申请的决定,使得在保证任意两条航线不相交的情况下,被批准的申请尽量多。输入格式第1行,一个整数N,表示城市数。第2行到第n+1行,每行两个整数,中间用1个空格隔开,分别表示南岸和

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题连接

Palmia国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市

北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定,使得在保证任意两条航线不相交的情况下,被批准的申请尽量多。

输入格式
第1行,一个整数N,表示城市数。

第2行到第n+1行,每行两个整数,中间用1个空格隔开,分别表示南岸和北岸的一对友好城市的坐标。

输出格式
仅一行,输出一个整数,表示政府所能批准的最多申请数。

数据范围
1≤N≤5000,
0≤xi≤10000
输入样例:

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出样例:

4

题解
先按照y排序然后对x求最长上升子序列

#include<bits/stdc++.h>
#include<cmath>
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef struct Node * pnode;
const int N = 1e1 + 10;
const int M = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int Mod = 4e8;
PII a[N];
bool cmp(const PII &a,const PII &b){ 
   
    return a.y < b.y;
}
int f[N];
int main(){ 
   
    int n,x,y;
    cin>>n;
    for(int i = 0;i < n;i ++)
    { 
   
        cin>>a[i].x>>a[i].y;
    }
    sort(a,a + n,cmp);
// for(int i = 0;i < n;i ++){ 
   
// a[i].x = i;
// cout<<a[i].x<<endl;
// }
    f[0] = 1;
    int res = 0;
    for(int i = 1;i < n;i ++){ 
   
        for(int j = 0;j < i;j ++){ 
   
            if(a[j].x < a[i].x){ 
   
                f[i] = max(f[i],f[j]);
            }
        }
        f[i] += 1;
        res = max(res,f[i]);
    }
    cout<<res<<endl;
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168900.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 作为程序员,你真的刻意练习了吗

    点击上方☝Java编程技术乐园,轻松关注!及时获取有趣有料的技术文章我真的刻意练习了吗刻意练习真的很重要,作为一名程序员,在读完这本书之后,也听了有关这本书的一些解读。有一些自己的感受。我是大四的下学期开始健身的,不到三个月的时间,能明显感觉到自己有了胸肌和腹肌。而在没有去健身房之前,平时也会去跑跑步,去操场上玩玩双杆,然后做几个引体向上,在宿舍也做几个俯卧撑,但是这些练…

  • lora协议不属于lpwan_哪种协议用于wan

    lora协议不属于lpwan_哪种协议用于wan考虑使用LoRaWAN部署您的物联网解决方案?倘若您正在开发用于工业或企业用途的专用网络解决方案,那么您需要了解此技术的一些限制(以及在许多情况下将为您提供更好服务的替代协议)。在本文中,我们将深入探讨:LoRa与LoRaWAN的区别LoRaWAN如何运作LoRaWANA,B和C类啁啾率,处理增益和正交性利用LoRaWAN构建专用网络的障碍另一种解决方案:SymphonyLinkLoRa与Lo…

  • 宠物社区小程序_宠物论坛哪个好

    宠物社区小程序_宠物论坛哪个好微信小程序宠物论坛6个人主页页面JS部分constdb=wx.cloud.database()Page({data:{openid:””,nickname:””,heads:””},onLoad:function(options){constopenid=options.idthis.setData({openid:openid})console.log(this.data.openid)d

  • 阿里云ssl证书过期_阿里云acp证书含金量

    阿里云ssl证书过期_阿里云acp证书含金量阿里云提示内容如下:【阿里云】尊敬的:您域名com使用的SSL证书cert-还有1天过期,过期时间2021-04-21。为防止业务受影响,请提前5个工作日续费并更新证书。请尽快登陆控制台处。这是阿里云的SSL证书产品的到期通知,SSL证书主要用于HTTPS加密协议场景包括,电子商务、微信小程序、微信公众号、APP、公司网站等。SSL证书到期后会让对应的项目立即暂停服务,比如微信小程序就会立即停止服务,用户不能正常使用小程序,其它的场景也一样,所以SSL证书到期之前必须要尽快办理续费!SSL证

  • HOJ 2245 浮游三角胞(数学啊 )

    HOJ 2245 浮游三角胞(数学啊 )

  • 【Qt】Qt的线程(两种QThread类的详细使用方式)「建议收藏」

    【Qt】Qt的线程(两种QThread类的详细使用方式)「建议收藏」Qt提供QThread类以进行多任务处理。与多任务处理一样,Qt提供的线程可以做到单个线程做不到的事情。例如,网络应用程序中,可以使用线程处理多种连接器。QThread继承自QObject类,且提供QMutex类以实现同步。线程和进程共享全局变量,可以使用互斥体对改变后的全局变量值实现同步。因此,必须编辑全局数据时,使用互斥体实现同步,其它进程则不能改变或浏览全局变量值。什么是互斥体?…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号