#include<bits/stdc++.h>
using namespace std;

const int N=5e3+10;
int n,dp[N],len,x,y;
struct Friendly_City{
	int k,l;
}a[N];

bool cmp(Friendly_City x,Friendly_City y)
{
	return x.k<y.k;
}

int main()
{
	cin>>x>>y;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&a[i].k,&a[i].l);
	}
	sort(a+1,a+n+1,cmp);
	dp[++len]=a[1].l;
	for(int i=1;i<=n;++i)
	{
		if(dp[len]<a[i].l)
		{
			dp[++len]=a[i].l;
		}
		else
		{
			int upd=upper_bound(dp+1,dp+len+1,a[i].l)-dp;
			dp[upd]=a[i].l;
		}
	}
	printf("%d",len);
	return 0;
}

这题实际做起来不难，但是思路很恶心。

比如说，一开始看到交叉瞬间不想做了，交叉是个啥？怎么做。

思路：

按照北岸排个序，接下来直接套LIS的模板即可

#include<bits/stdc++.h>
using namespace std;
struct uuu
{
	long long x,y;
};
long long dp[5001];
bool cmp(uuu a,uuu b)
{
	return a.x<b.x;
}
int main()
{
	long long n;
	cin>>n>>n>>n;
	uuu a[n+1];
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
		dp[i]=1;
	}
	sort(a+1,a+1+n,cmp);
	long long maxn=0;
	for(long long i=2;i<=n;i++)
	{
		for(long long j=1;j<i;j++)
		{
			if(a[i].y>a[j].y)
			{
				dp[i]=max(dp[i],dp[j]+1);
				maxn=max(dp[i],maxn);
			}
		}
	}
	cout<<maxn;
}

P1229 友好城市

看着这题,一脸懵逼:啥是交叉?可能只有我会一脸懵逼

A    B
 \   |
  \  |
   \ | 
    \|
     |
     |\
     | \
     B  A

如果有一条已经被批准的航道,它的南北坐标为N1,S1;

则第二条$N2<N1,S2>S1$的航道就会发生交叉。

思路

按北岸坐标大小对城市进行排序,来保证北岸序列单调上升,然后,南岸序列的最长上升子序列长度就是能够批准的航线条数。

代码:

#include <iostream>
#include <algorithm>
using namespace std;

int ans,n,a[200001];

struct tag
{
	int south,north;
};
tag c[200001];

bool cmp(tag &a,tag &b)
{
	return a.south < b.south;
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> c[i].south >> c[i].north;
	}
	sort(c + 1,c + n + 1,cmp);//排序south
	for(int i = 1;i <= n;i++)
	{
		if(a[ans] < c[i].north)
		{
			a[++ans] = c[i].north;
		}
		else
		{
			*lower_bound(a + 1,a + ans + 1,c[i].north) = c[i].north;
		}
	}
	cout << ans;
	return 0;
}