P2782 友好城市

线性dp水题

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n,ans=1;
int d[200005];
struct node{
	int z,y;
}a[200005];

bool cmp(node a,node b){
	return a.z<b.z;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].z,&a[i].y);
	}
	sort(a+1,a+1+n,cmp);
	d[1]=a[1].y;
    for (int i=2;i<=n;i++){
        if (a[i].y>=d[ans]){
			d[++ans]=a[i].y;
		}
        else{
            int j=upper_bound(d+1,d+ans+1,a[i].y)-d;//lower_bonud
            d[j]=a[i].y; 
        }
    }
    printf("%d
",ans);
	return 0;
}