题解 P2782 【友好城市】

yyy2015c01 · 2016-08-13 00:25:02 · 题解

聪明的你，告诉我，按照y拍完序之后和最长不下降子序列有什么区别呢？

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
struct city {
    int x;
    int y;
}citys[5001];
int f[5001]={0};
bool comp(const city & a,const city & b) {
    return a.x<b.x;
}
int main () {
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d%d",&citys[i].x,&citys[i].y);
        f[i]=1;
    }
    sort(citys+1,citys+1+n,comp);
    int maxnum=0;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<i;j++) {
            if (citys[j].y<citys[i].y) {
                f[i]=max(f[i],f[j]+1);
            }
        }
        maxnum=max(maxnum,f[i]);
    }
    printf("%d\n",maxnum);
    return 0;
}