题目：友好城市

分析一下可以转化为：选取最多的点对，使得点对之间连线没有交点，没有交点说明什么，假设选定第i组，则对于任意的j，一定满足a[i].l<a[j].l && a[i].r<a[j].r或者a[i].l>a[j].l && a[i].r>a[j].r，那么就可以先按左端点排序，再求一遍最长上升子序列，就解决了。

其实也可以继续优化到nlogn，但是没必要，对于本题的5000，n^2复杂度已经足以。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

const int N=5e3+5;

using namespace std;

struct pos

{

    int l,r;

    pos(int ll,int rr)

    {

        l=ll;r=rr;

    }

    pos(){

    }

    friend bool operator < (pos a,pos b)

    {

        return a.l<b.l;

    }

}e[N];

int n,f[N];

int main()

{

    scanf("%d",&n);

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

    {

        int l,r;

        scanf("%d %d",&l,&r);

        e[i]=pos(l,r);

    }

    sort(e+1,e+1+n);

    int ret=0;

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

    {

        f[i]=1;

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

            if(e[i].r>e[j].r)

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

        ret=max(ret,f[i]);

    }

    printf("%d\n",ret);

    return 0;

}

巴特西

2022春每日一题：Day 27

题目：友好城市

最新文章

热门文章