题解 P2782 【友好城市】

· · 题解

此题其实就是在求最长上升子序列的长度，先将一岸的城市排序，如果每对友好城市的航线都要不冲突的话，

那么它们对应的友好城市必须呈上升趋势，也就是排在越前面的城市，所对应的友好城市也要越靠前

#include<bits/stdc++.h>
using namespace std;
int n,N[5500],S[5500],i,f[5500],maxn,j;
void qs(int ll,int rr)//对N岸的城市进行排序，同时它们所对应的友好城市跟着移动 
{
    int key1,key,l,r;
    key=N[ll];
    key1=S[ll];
    l=ll;
    r=rr;
    while(l<r)
    {
        while(N[r]>=key&&r>l) r--;
        if(r>l) N[l]=N[r],S[l]=S[r],l++;
        while(N[l]<=key&&l<r) l++;
        if(r>l) N[r]=N[l],S[r]=S[l],r--;
        N[l]=key,S[l]=key1;
    }
    if(ll<l-1) qs(ll,l-1);
    if(rr>r+1) qs(r+1,rr);
}
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&N[i],&S[i]);
    qs(1,n);
    f[1]=1;
    for(i=1;i<=n;i++)//i代表第i个城市 
        for(j=i;j>=1;j--)//j用来循环第i个城市之前的城市 
            if(S[i]>S[j])//如果i对应的友好城市大于循环到的城市 
                f[i]=max(f[j]+1,f[i]);/*求以第i个城市作为最后批准的城市所能达到的最大批准数，

比较第j个城市的最大批准数（因为j是倒数第二个批准，所以要在原来的基础上+1），这时的f[i]代表的是目前已知的最大批准数*/ for(i=1;i<=n;i++)//由于不清楚以哪个城市作为最后一个批准的城市才能是批准个数达到最大，所以循环一遍取最大值

    if(maxn<f[i]) maxn=f[i];

printf("%d",maxn);//输出最大批准数 

return 0;

}