【BZOJ1109】[POI2007]堆积木Klo

Description

　　Mary在她的生日礼物中有一些积木。那些积木都是相同大小的立方体。每个积木上面都有一个数。Mary用他的所有积木垒了一个高塔。妈妈告诉Mary游戏的目的是建一个塔，使得最多的积木在正确的位置。一个上面写有数i的积木的正确位置是这个塔从下往上数第i个位置。Mary决定从现有的高塔中移走一些，使得有最多的积木在正确的位置。请你告诉Mary她应该移走哪些积木。

Input

　　第一行为一个数n，表示高塔的初始高度。第二行包含n个数a1,a2,...,an，表示从下到上每个积木上面的数。(1<=n<=100000,1<=ai<=1000000)。

Output

　　注意：请输出最多有多少点可以处在正确位置

Sample Input

5
1 1 2 5 4

Sample Output

HINT

技术分享

题解：将每个格子看成一个二维平面上的点，那么用f[j]表示答案，j能转移到i当且仅当j<i&&a[j]<a[i]&&j-a[j]<=i-a[i]，然后我发下这是个三维偏序，然后就上了一个cdq分治过了。

结果看题解发现，a[j]<a[i]&&j-a[j]<=i-a[i]就一定说明j<i，所以二维偏序就行了，感觉自己真是个沙茶~

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn=1000010;int n,m,ans,now;int s[maxn],vis[maxn],v[maxn],x[maxn],y[maxn],p[maxn],f[maxn];bool cmp(int a,int b){	return (y[a]==y[b])?(a<b):y[a]<y[b];}void updata(int x,int v){	for(int i=x;i<=m;i+=i&-i)	{		if(vis[i]<now)	vis[i]=now,s[i]=-1<<30;		s[i]=max(s[i],v);	}}int query(int x){	int ret=-1<<30,i;	for(i=x;i>0;i-=i&-i)	{		if(vis[i]<now)	vis[i]=now,s[i]=-1<<30;		ret=max(ret,s[i]);	}	return ret;}void solve(int l,int r){	if(l==r)	return ;	int mid=l+r>>1,h1=l,h2=mid+1,i;	solve(l,mid);	sort(p+mid+1,p+r+1,cmp);	now++;	while(h1<=mid||h2<=r)	{		if(h1<=mid&&(h2>r||y[p[h1]]<=y[p[h2]]))	updata(x[p[h1]],f[p[h1]]),h1++;		else	f[p[h2]]=max(f[p[h2]],query(x[p[h2]]-1)+1),h2++;	}	for(i=mid+1;i<=r;i++)	p[i]=i;	solve(mid+1,r);	sort(p+l,p+r+1,cmp);}int main(){	scanf("%d",&n);	int i;	for(i=1;i<=n;i++)	{		scanf("%d",&x[i]),m=max(m,x[i]),y[i]=i-x[i],p[i]=i;		if(x[i]<=i)	f[i]=1;		else	f[i]=-1<<30;	}	solve(1,n);	for(i=1;i<=n;i++)	ans=max(ans,f[i]);	printf("%d",ans);	return 0;}

【BZOJ1109】[POI2007]堆积木Klo 二维偏序

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【BZOJ1109】[POI2007]堆积木Klo 二维偏序