“我有个愿望，我希望穿越一切找到你。”
这是个二维平面世界，平面上有n个特殊的果实，我从(0,0)点出发，希望得到尽量多的果实，但是出于某种特殊的原因，我的运动方式只有三种（假设当前我在(x,y)）：
1、我可以走到(x+1,y)
2、我可以走到(x,y+1)
3、我可以走到(x+1,y+1)
现在我需要你的帮助，帮我找出我最多能够得到多少个果实。
对于70%的数据1<=n<=1000
对于100%的数据1<=n<=100000，-10^9<=x,y<=10^9
一眼题，看错题的我只能憋屈会儿了。
不能下降走或者往右走，选择x（或y）升序排序，然后y（或x）做最长不下降子序列。
#include<bits/stdc++.h> using namespace std; #define N 100010 int n,ans,cnt,top,num=0; int s[N]; struct email { int x,y; }a[N]; inline void read(int &x) { x=0;int f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} x*=f; } bool cmp(email a,email b) { return a.y<b.y; } int main() { read(n); for(int i=1;i<=n;i++) { int x,y; read(x);read(y); if(x<0||y<0)continue; a[++cnt].x=x;a[cnt].y=y; } sort(a+1,a+1+cnt,cmp); for(int i=1;i<=cnt;i++) { if(a[i].x>=s[top])s[++top]=a[i].x; else { int pos=lower_bound(s+1,s+1+top,a[i].x)-s; s[pos]=a[i].x; } } printf("%d\n",top); return 0; }
原文：https://www.cnblogs.com/NSD-email0820/p/9797235.html