这该死的码农题……
题解在这儿->
1 //minamoto 2 #include 3 #include 4 #include 5 #include 6 #include 7 #define inf 0x3f3f3f3f 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 10 char buf[1<<21],*p1=buf,*p2=buf; 11 inline int read(){ 12 #define num ch-'0' 13 char ch;bool flag=0;int res; 14 while(!isdigit(ch=getc())) 15 (ch=='-')&&(flag=true); 16 for(res=num;isdigit(ch=getc());res=res*10+num); 17 (flag)&&(res=-res); 18 #undef num 19 return res; 20 } 21 const int N=100005; 22 int n,jsx,jsy,js1,js2; 23 struct node{ int x,y,b1,b2,id;}p[N]; 24 int bx[N],by[N],bb1[N],bb2[N]; 25 int up[N],lup[N],rup[N],f[N],Tx[N],Tb1[N],Tb2[N],bj[N],tx[N],ty[N],gup[N],bup[N]; 26 bool cmpy(node a,node b){ return a.y>b.y;} 27 bool cmpx(node a,node b){ return a.x
iny[N]; 29 void prework(){ 30 sort(bx+1,bx+1+n),sort(by+1,by+1+n); 31 sort(bb1+1,bb1+1+n),sort(bb2+1,bb2+1+n); 32 jsx=unique(bx+1,bx+1+n)-bx-1; 33 jsy=unique(by+1,by+1+n)-by-1; 34 js1=unique(bb1+1,bb1+1+n)-bb1-1; 35 js2=unique(bb2+1,bb2+1+n)-bb2-1; 36 for(int i=1;i<=n;++i){ 37 p[i].x=lower_bound(bx+1,bx+1+jsx,p[i].x)-bx,tx[i]=p[i].x; 38 p[i].y=lower_bound(by+1,by+1+jsy,p[i].y)-by,ty[i]=p[i].y; 39 p[i].b1=lower_bound(bb1+1,bb1+1+js1,p[i].b1)-bb1; 40 p[i].b2=lower_bound(bb2+1,bb2+1+js2,p[i].b2)-bb2; 41 } 42 sort(p+1,p+1+n,cmpy); 43 for(int i=1;i<=n;++i){ 44 int k=p[i].id; 45 up[k]=Tx[p[i].x],lup[k]=Tb1[p[i].b1],rup[k]=Tb2[p[i].b2]; 46 Tx[p[i].x]=Tb1[p[i].b1]=Tb2[p[i].b2]=k; 47 } 48 sort(p+1,p+1+n,cmpx); 49 for(int i=1;i<=n;++i) 50 iny[p[i].y].push_back(p[i].id); 51 } 52 void print(int num){ 53 int y=ty[num],sz=iny[y].size(),nxt=bj[num]; 54 if(num!=n) printf("%d ",num); 55 if(tx[nxt]
tx[num]) printf("%d ",iny[y][i]); 58 for(int i=sz-1;~i;--i) 59 if(tx[iny[y][i]] =tx[nxt]) printf("%d ",iny[y][i]); 60 } 61 else if(tx[nxt]>tx[num]){ 62 for(int i=sz-1;~i;--i) 63 if(tx[iny[y][i]] tx[num]&&tx[iny[y][i]]<=tx[nxt]) printf("%d ",iny[y][i]); 66 } 67 if(bup[nxt]) print(bup[nxt]); 68 } 69 void work1(){ 70 prework(); 71 for(int y=jsy;y;--y){ 72 int kmx=0,kbj=0,sz=iny[y].size(); 73 for(int i=0;i gup[k]) gup[k]=f[up[k]],bup[k]=up[k]; 76 if(lup[k]&&f[lup[k]]>gup[k]) gup[k]=f[lup[k]],bup[k]=lup[k]; 77 if(rup[k]&&f[rup[k]]>gup[k]) gup[k]=f[rup[k]],bup[k]=rup[k]; 78 f[k]=kmx,bj[k]=kbj; 79 if(sz-i+gup[k]>kmx) kmx=sz-i+gup[k],kbj=k; 80 } 81 kmx=kbj=0; 82 for(int i=sz-1;~i;--i){ 83 int k=iny[y][i]; 84 if(kmx>f[k]) f[k]=kmx,bj[k]=kbj; 85 if(gup[k]+1>f[k]) f[k]=gup[k]+1,bj[k]=k; 86 if(i+1+gup[k]>kmx) kmx=i+1+gup[k],kbj=k; 87 } 88 } 89 printf("%d\n",f[n]-1),print(n),puts(""); 90 } 91 int S,T,s,t,ans,tot=1; 92 int ok[N],du[N],cur[N],head[N],Next[N*10],ver[N*10],edge[N*10],dep[N]; 93 queue q; 94 inline void adde(int u,int v,int e){ 95 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 96 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=0; 97 } 98 inline void add(int u,int v){ 99 for(int i=head[u];i;i=Next[i]) if(ver[i]==v) return;100 ok[v]=1,++du[v],--du[u],adde(u,v,inf);101 }102 void calc(int y,int i){103 int sz=iny[y].size(),num=iny[y][i];104 for(int j=0;j 0?ans+=du[i],adde(S,i,du[i]):adde(i,T,-du[i]);162 while(bfs()) ans-=dfs(S,inf);163 printf("%d\n",ans);164 }165 int main(){166 //freopen("testdata.in","r",stdin);167 n=read();168 for(int i=1;i<=n;++i){169 bx[i]=p[i].x=read(),by[i]=p[i].y=read();170 bb1[i]=p[i].b1=p[i].y-p[i].x,bb2[i]=p[i].b2=p[i].x+p[i].y;171 p[i].id=i;172 }173 ++n,p[n].id=n;174 work1(),work2();175 return 0;176 }