Codeforces 4D

题解： 二维最长上升子序列输出路径。常规操作先按 $w$w排序。然后 $O\left(n^2\right)$O(n2)暴力即可。
这题没看数据范围直接莽了 $O\left(nlogn\right)$O(nlogn)的做法，被卡了三发后逐渐明白错误原因(也可能是我根本就不会这题 $O\left(nlogn\right)$O(nlogn)做法)。
显然的是，每个 $w$w下的 $h$h在答案中只会出现一个，所以刚开始就直接只保留每个 $w$w下的最小 $h$h。
但是有错误数据：

3 1 2
2 5
3 3
3 6
4 7

保留每个 $w$w下的最小 $h$h的结果为：

1 2

2 5
3 3
4 7

得到：

1 2
2 5 / 3 3
4 7

实际结果：

1 2
2 5
3 6 (被删去了)
4 7

所以好像只能 $O\left(n^2\right)$O(n2)暴力~

代码：

#include<bits/stdc++.h>
using namespace std;
 
const int N = 5010;
int f[N], pre[N];
int n, m, w, h;
struct Poi{
	int w, h, num;
	bool operator < (const Poi &A) const {
		if(w == A.w) return h < A.h;
		return w < A.w;
	}
}p[N]; int g;
 
int main()
{
	scanf("%d%d%d", &m, &w, &h);
	for(int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		if(a > w && b > h) p[++n] = {a, b, i};
	}
	sort(p + 1, p + 1 + n);
	
	int Ma = 0;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < i; j++) 
			if(p[i].w > p[j].w && p[i].h > p[j].h && f[j] + 1 > f[i]) {
				pre[i] = j;
				f[i] = f[j] + 1; 
				if(f[i] > f[Ma]) Ma = i;
			}
 
	vector<int> ans;
	for(int i = Ma; i; i = pre[i]) ans.push_back(p[i].num);
	reverse(ans.begin(), ans.end());
	int len = ans.size();
	printf("%d\n", len);
	for(int i = 0; i < len; i++) printf("%d%c", ans[i], " \n"[i == len - 1]);
	
	return 0; 
}