题面
“我有个愿望,我希望穿越一切找到你。”
这是个二维平面世界,平面上有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的LIS,利用树状数组优化。
#include <bits/stdc++.h>
using namespace std;
struct haha{
int x;
int y;
}lala[],fin[],tmp[];
bool cmp(haha x,haha y)
{
if(x.x==y.x) return x.y<y.y;
return x.x<y.x;
}
bool cmp2(haha x,haha y)
{
if(x.y==y.y) return x.x<y.x;
return x.y<y.y;
}
int n;
inline int lowbit(register int x)
{
return x&(-x);
}
int c[];
inline void add(register int x,register int v)
{
while(x<=n){
c[x]=max(c[x],v);
x+=lowbit(x);
}
return;
}
inline int ask(int x)
{
register int res=;
while(x>){
res=max(res,c[x]);
x-=lowbit(x);
}
return res;
}
int f[];
int main()
{
cin>>n;
int num=;
for(register int i=;i<=n;i++){
int a,b;
scanf("%d%d",&a,&b);
if(a<||b<){
continue;
}
lala[++num].x=a;
lala[num].y=b;
}
n=num;
sort(lala+,lala++n,cmp);
for(register int i=;i<=n;i++){
tmp[i]=lala[i];
tmp[i].x=i;
}
sort(tmp+,tmp++n,cmp2);
tmp[].y=;
for(register int i=;i<=n;i++){
fin[i]=tmp[i];
if(tmp[i].y==tmp[i-].y){
fin[i].y=fin[i-].y;
}
else{
fin[i].y=i;
}
}
sort(fin+,fin++n,cmp);
for(register int i=;i<=n;i++){
int now=fin[i].y;
int found=ask(now);
int op=found+;
f[i]=op;
add(now,op);
}
register int maxn=;
for(register int i=;i<=n;i++){
maxn=max(maxn,f[i]);
}
cout<<maxn;
}
/*
8
0 1
1 0
1 5
2 5
3 4
3 1
5 1
5 4
*/