题解 P2782 【友好城市】

doby · 2016-08-20 15:44:35 · 题解

早期的NOIP数据有点弱，在没对北岸排序的情况下直接搜南岸的最长不子降序列，还是过了……

#include<iostream>
using namespace std;
int a[10001],b[10001],c[10001],n,s,ans=0;
void qsort(int l,int r)//排序
{
    int i,j,mid,p;
    i=l,j=r,mid=a[(l+r)/2];
    while(i<=j)
    {
        while(a[i]<mid){i++;}
        while(a[j]>mid){j--;}
        if(i<=j){p=a[i],a[i]=a[j],a[j]=p,p=b[i],b[i]=b[j],b[j]=p,i++,j--;}
    }
    if(i<r){qsort(i,r);}
    if(l<j){qsort(l,j);}
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i]>>b[i];}qsort(1,n);
    for(int i=1;i<=n;i++)
    {
        s=0;for(int j=1;j<=i-1;j++){if(s<c[j]&&b[i]>b[j]){s=c[j];}}//求南岸的最长不降子序列……
        c[i]=s+1;if(c[i]>ans){ans=c[i];}
    }
    cout<<ans;
}