luogu P2304 [NOI2015] 小园丁与老司机

本文主要是介绍luogu P2304 [NOI2015] 小园丁与老司机，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
非常码农的二合一题。
首先第一问看上去非常simple。因为只能往左，往右，和往上走(包括左上，上，右上)，往上走显然是没有后效性的。而往左和往右因为每一层最多1000个，所以直接枚举从上一层跑过来的地方转移即可，时间复杂度\(O(1000n)\)
然后第二问只要按照我们dp的过程输出即可。
为了找到这些可能走过的向上边，我们反着做一遍dp，然后枚举这样的边，如果这条边连接的两个顶点的答案和为最大值，那么这条边就可能在答案中。
然后我们要解决的相当于是一个DAG上的每条边流量下界为\(1\)，上界为\(\infty\)的有源汇上下界网络流问题。跑个dicnic即可，时间复杂度可以感性理解为\(O(n\sqrt n)\)。
似乎只有一种路径的时候没有限制只有1000个同一行，但是出题人没卡
代码成屎山了。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define ll long long
#define db double
#define lb long db
#define N (50000+5)
#define M (30000+5)
#define K (6)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define ull unsigned ll
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (1ll*rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;map<int,int> F1,F2,F3;
int n,m,k,x,y,z,dp[N],f[N],R,L1[N],L2[N],g[N],ToT,st[N],H,C[N],Ch,Si[N];I void Fp(){while(Ch) st[++H]=C[Ch--];}
struct Node{int x,y,id;}S[N];I bool cmp(Node x,Node y){return x.y^y.y?x.y<y.y:x.x<y.x;}
struct yyy{int to;ll w;int z;}tmp;struct ljb{int head=1,h[N];yyy f[N<<3];I void add(int x,int y,ll z){f[++head]=(yyy){y,z,h[x]};h[x]=head;}}s;I void add(int x,int y,ll z,int w){/*w&&(cerr<<x<<' '<<y<<' '<<z<<'\n',0);*/s.add(x,y,z);s.add(y,x,0);Si[y]+=w;Si[x]-=w;}
namespace Dicnic{
	queue<int> Q;int d[N],Ns[N],S,T,SS,TT;I void Del(int x){s.h[x]=s.f[s.h[x]].z;}
	I int BFS(){
		Me(d,0x3f);d[S]=0;Ns[S]=s.h[S];Q.push(S);while(!Q.empty()) {int x=Q.front();Q.pop();for(int i=s.h[x];i;i=tmp.z){tmp=s.f[i];
				if(!tmp.w||d[tmp.to]<=d[x]+1) continue;d[tmp.to]=d[x]+1;Q.push(tmp.to);Ns[tmp.to]=s.h[tmp.to];if(tmp.to==T) return 1;
		}}return 0;
	}
	I ll DFS(int x,ll sum){if(x==T) return sum;ll k,pus=0;yyy tmp;for(int i=Ns[x];i;i=tmp.z){tmp=s.f[i];Ns[x]=i;if(!tmp.w||d[tmp.to]!=d[x]+1) continue;k=DFS(tmp.to,min(tmp.w,sum));if(!k) d[tmp.to]=1e9;sum-=k;pus+=k;s.f[i].w-=k;s.f[i^1].w+=k;if(!sum) break;}return pus;}
	I ll calc(){
		ll ToT=0;int i;SS=0;TT=n+1;S=n+2;T=n+3;for(i=0;i<=n+1;i++) Si[i]>0?add(S,i,Si[i],0):add(i,T,-Si[i],0);add(TT,SS,1e18,0);while(BFS()) ToT+=DFS(S,1e18);ToT=s.f[s.head].w;
		Del(S=TT);Del(T=SS);while(BFS()) ToT-=DFS(S,1e18);return ToT;
	}
}
int main(){
	freopen("1.in","r",stdin);
	int i,j,h;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%d",&S[i].x,&S[i].y),S[i].id=i;sort(S+1,S+n+1,cmp);dp[n+1]=-1e9;
	Me(dp,-0x3f);dp[0]=g[0]=0;F1[0]=F2[0]=F3[0]=0;Me(L1,-1);Me(L2,-1);for(i=1;i<=n;i=R+1) {
		for(R=i+1;R<=n;R++) if(S[R].y^S[i].y) break;R--;for(j=i;j<=R;j++) x=(F1.count(S[j].x)?F1[S[j].x]:n+1),y=(F2.count(S[j].y+S[j].x)?F2[S[j].y+S[j].x]:n+1),z=(F3.count(S[j].y-S[j].x)?F3[S[j].y-S[j].x]:n+1),g[j]=dp[j]=max(dp[x],max(dp[y],dp[z]))+1,L1[j]=((dp[x]+1)^dp[j]?((dp[y]+1)^dp[j]?z:y):x);
		for(j=i;j<=R;j++) for(h=j+1;h<=R;h++) g[j]+h-i>dp[h]&&(dp[h]=g[j]+h-i,L2[h]=j);for(j=i;j<=R;j++) for(h=i;h<j;h++) g[j]+R-h>dp[h]&&(dp[h]=g[j]+R-h,L2[h]=j);
		for(j=i;j<=R;j++) (!F1.count(S[j].x)||dp[F1[S[j].x]]<dp[j])&&(F1[S[j].x]=j),(!F2.count(S[j].y+S[j].x)||dp[F2[S[j].y+S[j].x]]<dp[j])&&(F2[S[j].y+S[j].x]=j),(!F3.count(S[j].y-S[j].x)||dp[F3[S[j].y-S[j].x]]<dp[j])&&(F3[S[j].y-S[j].x]=j);
	}for(i=1;i<=n;i++) ToT=max(ToT,dp[i]);printf("%d\n",ToT);for(i=1;i<=n;i++) if(dp[i]==ToT) {x=i;break;}while(x){ st[++H]=x;
		if(~L2[x]) {if(x>L2[x]){ for(i=x-1;i>L2[x];i--) st[++H]=i;for(i=L2[x];i&&S[i].y==S[x].y;i--) C[++Ch]=i;Fp();}else {for(i=x+1;i<L2[x];i++) st[++H]=i;for(i=L2[x];S[i].y==S[x].y;i++) C[++Ch]=i;Fp();}x=L2[x];};x=L1[x];
	}while(H) printf("%d ",S[st[H--]].id);Pc('\n');F1.clear();F2.clear();F3.clear();
	for(i=n;i;i=R-1){
		for(R=i-1;R;R--) if(S[R].y^S[i].y) break;R++;for(j=R;j<=i;j++) x=(F1.count(S[j].x)?F1[S[j].x]:0),y=(F2.count(S[j].y+S[j].x)?F2[S[j].y+S[j].x]:0),z=(F3.count(S[j].y-S[j].x)?F3[S[j].y-S[j].x]:0),g[j]=f[j]=max(x,max(y,z))+1;
		for(j=R;j<=i;j++) for(h=j+1;h<=i;h++) f[h]=max(f[h],g[j]+i-j);for(j=R;j<=i;j++) for(h=R;h<j;h++) f[h]=max(f[h],g[j]+j-R);
		for(j=R;j<=i;j++) F1[S[j].x]=max(F1[S[j].x],f[j]),F2[S[j].x+S[j].y]=max(F2[S[j].x+S[j].y],f[j]),F3[S[j].y-S[j].x]=max(F3[S[j].y-S[j].x],f[j]);
	}
	F1.clear();F2.clear();F3.clear();F1[0]=F2[0]=F3[0]=0;for(i=1;i<=n;i++) {
		F1.count(S[i].x)&&ToT==f[i]+dp[F1[S[i].x]]&&(add(F1[S[i].x],i,1e9,1),0);F2.count(S[i].x+S[i].y)&&ToT==f[i]+dp[F2[S[i].x+S[i].y]]&&(add(F2[S[i].x+S[i].y],i,1e9,1),0);F3.count(S[i].y-S[i].x)&&ToT==f[i]+dp[F3[S[i].y-S[i].x]]&&(add(F3[S[i].y-S[i].x],i,1e9,1),0);
		F1[S[i].x]=F2[S[i].x+S[i].y]=F3[S[i].y-S[i].x]=i;
	}for(i=1;i<=n;i++) add(i,n+1,1e9,0),add(0,i,1e9,0);printf("%d\n",Dicnic::calc());
}

这篇关于luogu P2304 [NOI2015] 小园丁与老司机的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！