题目描述

“我有个愿望，我希望穿越一切找到你。”

这是个二维平面世界，平面上有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

解法

离散化后动态规划，数据结构进行维护。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;const char* fin="find.in";const char* fout="find.out";const int inf=0x7fffffff;const int maxn=100007,maxt=maxn*4;int n,i,j,k,num,tot,totx,toty;int fi[maxn],ne[maxn],la[maxn],en[maxn];struct point{    int x,y;}a[maxn];bool cmp(point a,point b){    return a.y
          
           v2 || r
           
            =v1 && r<=v2) return c[t]; return max(getmax(l,mid,t*2,v1,v2),getmax(mid+1,r,t*2+1,v1,v2));}void change(int l,int r,int t,int v1,int v2,int v){ int mid=(l+r)/2; markdown(l,r,t); if (l>v2 || r
            
             =v1 && r<=v2){ mark[t]=v; markdown(l,r,t); return; } change(l,mid,t*2,v1,v2,v); change(mid+1,r,t*2+1,v1,v2,v); c[t]=max(c[t*2],c[t*2+1]);}int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%d",&n); for (i=1;i<=n;i++){ scanf("%d%d",&j,&k); if (j>=0 && k>=0){ num++; a[num].x=j; a[num].y=k; } } sort(a+1,a+num+1,cmp); int last=a[1].y; a[1].y=1; for (i=2;i<=num;i++) if (a[i].y!=last) last=a[i].y,a[i].y=a[i-1].y+1; else a[i].y=a[i-1].y; toty=a[num].y; sort(a+1,a+num+1,cmp1); last=a[1].x; a[1].x=1; add_line(a[1].x,a[1].y); for (i=2;i<=num;i++){ if (a[i].x!=last) last=a[i].x,a[i].x=a[i-1].x+1; else a[i].x=a[i-1].x; add_line(a[i].x,a[i].y); } totx=a[num].x; for (i=1;i<=totx;i++){ for (k=fi[i];k;k=ne[k]){ j=la[k]; change(1,toty,1,j,toty,getmax(1,toty,1,1,j)+1); } } int ans=getmax(1,toty,1,1,toty); printf("%d",ans); return 0;}