自动搬运

查看原文

来自洛谷，原作者为

	lemondinosaur 那跑过去的昼夜是孤独的修炼

搬运于2025-08-24 22:15:48，当前版本为作者最后更新于2021-01-03 16:53:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门

---

考虑这个45度不是那么好搞，

那么将坐标系逆时针旋转45度，新坐标 $(x',y')$ 满足

$$x'=x \cos \theta +y \sin \theta,y'=y \cos \theta -x\sin \theta $$

$\frac{\sqrt{2}}{2}$ 为了方便可以直接约掉，就题论题就变成了 $(x+y,y-x)$

然后排序就是将横坐标作为第一关键字升序排序，

再将纵坐标作为第二关键字降序排序，这样就只用管纵坐标了

那问题就转换成最少用多少个不上升序列可以覆盖所有点

根据Dilworth定理也就是求最长上升子序列的长度

---

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=30011;
struct rec{int x,y;}a[N]; int n,b[N],len;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans; 
}
bool cmp(rec a,rec b){return a.x<b.x||(a.x==b.x&&a.y>b.y);} 
signed main(){
	n=iut();
	for (rr int i=1;i<=n;++i){
		rr int x=iut(),y=iut();
		a[i]=(rec){x+y,y-x};
	}
	sort(a+1,a+1+n,cmp);
	b[++len]=a[1].y;
	for (rr int i=2;i<=n;++i){
		if (a[i].y>b[len]) b[++len]=a[i].y;
		else b[lower_bound(b+1,b+1+len,a[i].y)-b]=a[i].y;
	}
	return !printf("%d",len);
}