P2782 友好城市

题目

题目链接

题解

最长上升子序列。

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

难点有二：

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

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

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

有关优化的代码及讲解。

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

代码 未优化

#include
#define PII pair 
#define x first
#define y second
using namespace std;

const int N = 1e5+10;

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

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

	sort (v.begin (), v.end ());
	
	for (int i = 0;i  a >> b,
		v.push_back ({a, b});

	sort (v.begin (), v.end ());
	
	for (int i = 0;i  d[len]) d[++len] = j;
		else d[binary_search (j)] = j;
	}
	
	cout