[数据结构与算法]P2782 友好城市

题目

题目链接

题解

最长上升子序列。

存在加强数据，动态规划的最长上升子序列只能过基础数据，$O(n^2)$。加强数据需要使用贪心优化的$O(nlogn)$做法。

难点有二：

1. 想到先排序；
2. 想到用最长上升子序列.

这种题想到先排序应该是要靠题量累积起来的，一开始我是直接按照输入顺序（即无序）进行遍历，要求只要第i个桥的两端城市坐标比第j个桥两端的城市坐标都大，那么就可以由第j个城市转移而来。

但是样例就错了，所以想到了先对一端的城市排序，先保证一端的城市是递增的，再对另一端进行上升子序列操作，这样就保证了另一端也是递增的了。

有关优化的代码及讲解。

导弹拦截题目的讲解，里面也讲解了优化的思考过程

代码

未优化

#include<bits/stdc++.h>
#define PII pair <int, int>
#define x first
#define y second
using namespace std;

const int N = 1e5+10;

int n, f[N], a, b, ans;
vector <PII> v;

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++)	
		cin >> a >> b,
		v.push_back ({a, b});

	sort (v.begin (), v.end ());
	
	for (int i = 0;i < n;i ++) {
		f[i] = 1;
		for (int j = 0;j < i;j ++)
			if (v[i].y > v[j].y) 
				f[i] = max (f[i], f[j] + 1);
		ans = max (ans, f[i]);
	}
	
	cout << ans << endl;

	return 0;
}

优化后

#include<bits/stdc++.h>
#define PII pair <int, int>
#define x first
#define y second
using namespace std;

const int N = 2e5+10;

int n, a, b, len;
int f[N], d[N];
vector <PII> v;

int binary_search (int x) { // 等价于lower_bound
	int m, l = 1, r = len;
	while (l < r) {
		m = l + r >> 1;
		if (d[m] >= x) r = m;
		else l = m + 1;
	}
	return l;
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++)	
		cin >> a >> b,
		v.push_back ({a, b});

	sort (v.begin (), v.end ());
	
	for (int i = 0;i < n;i ++) {
		int j = v[i].y;
		if (j > d[len]) d[++len] = j;
		else d[binary_search (j)] = j;
	}
	
	cout << len << endl;

	return 0;
}