P2782 友好城市（最长不下降子序列）

题目描述

有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的$N$个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航道不相交的情况下，被批准的申请尽量多。

输入格式

第1行，一个整数$N$，表示城市数。

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

输出格式

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

样例数据

输入

输出

分析

将一侧河岸的城市坐标有小到大进行排序，若其友好城市坐标是递增的，则其航道必定不相交。要求最多申请数即可转化为最长不下降子序列

代码

#include <bits/stdc++.h>

#define Enter puts("")

#define Space putchar(' ')

using namespace std;

typedef long long ll;

typedef double Db;

inline ll Read()

{

    ll Ans = 0;

    char Ch = getchar() , Las = ' ';

    while(!isdigit(Ch))

    {

        Las = Ch;

        Ch = getchar();

    }

    while(isdigit(Ch))

    {

        Ans = (Ans << 3) + (Ans << 1) + Ch - '0';

        Ch = getchar();

    }

    if(Las == '-')

        Ans = -Ans;

    return Ans;

}

inline void Write(ll x)

{

    if(x < 0)

    {

        x = -x;

        putchar('-');

    }

    if(x >= 10)

        Write(x / 10);

    putchar(x % 10 + '0');

}

struct N

{

    int South , North;

}a[100001];

inline bool Cmp(N x , N y)

{

    return x.South < y.South;

}

int Dp[100001];

int Maxn = -9999999;

int main()

{

    int n;

    n = Read();

    for(int i = 1; i <= n; i++)

    {

        a[i].South = Read();

        a[i].North = Read();

        Dp[i] = 1;

    }

    sort(a + 1 , a + n + 1 , Cmp);

    for(int i = 2; i <= n; i++)

        for(int j = 1; j <= i - 1; j++)

            if(a[i].North > a[j].North)

            {

                Dp[i] = max(Dp[i] , Dp[j] + 1);

                Maxn = max(Dp[i] , Maxn);

            }

    Write(Maxn);

    return 0;

}

巴特西

P2782 友好城市（最长不下降子序列）

题目描述

输入格式

输出格式

样例数据

分析

代码

最新文章

热门文章