信息学奥赛一本通T1263-友好城市

解题思路:转化为最长不下降子序列

注意事项:

参考代码:

#include<iostream>
#include<utility>
#include<algorithm>
using namespace std;
const int N = 5e3 + 10;
pair<int,int> p[N];
int n, a[N],f[N];
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> p[i].first >> p[i].second;
	sort(p + 1, p + n + 1);
	for(int i = 1; i <= n; i ++) a[i] = p[i].second;
	for(int i = 1; i <= n; i ++){
		f[i] = 1;
		for(int j = 1; j < i; j ++){
			if(a[j] <= a[i])
				f[i] = max(f[i],f[j] + 1);
		}
	}
	int res = 0;
	for(int i = 1; i <= n; i ++) res = max(res,f[i]);
	cout << res;
	return 0;
}