首页 > 代码库 > 【BZOJ4167】永远的竹笋采摘 分块+树状数组

【BZOJ4167】永远的竹笋采摘 分块+树状数组

 

【BZOJ4167】永远的竹笋采摘

技术分享

技术分享

题解:我们考虑有多少点对(a,b)满足a与b的差值是[a,b]中最小的。以为是随机数据,这样的点对数目可能很少,实测是O(n)级别的,那么我们已知了有这么多可能对答案造成贡献的点对,如何将它们求出来呢?

考虑分块,因为所有数大小在[1,n]中,我们可以对于每个块,预处理出整个块到所有数的最小差值。然后从右往左枚举每一个点,再枚举右面所有的块,如果这个块到当前数的差值比之前的要小,那就暴力进入块中扫一遍。与此同时,我们需要知道是否已经存在这样的点对,被当前的点对完全包含且差值更小。这个可以用树状数组搞定。

最后,我们得到所有的点对,问题就变成了在数轴上选取k个互部相交的线段,使得线段权值和最小。跑个DP就行了。

#include <cstdio>#include <cstring>#include <iostream>#include <cmath>#include <algorithm>using namespace std;const int maxn=60010;int n,m,B,cnt,minn;int s[maxn],v[maxn],p[maxn];int cls[250][maxn],f[2][maxn],to[500000],next[500000],head[maxn],val[500000];int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int z(int x){	return x>0?x:-x;}void updata(int x,int val){	for(int i=x;i<=n;i+=i&-i)	s[i]=min(s[i],val);}int query(int x){	int i,ret=1<<30;	for(i=x;i;i-=i&-i)	ret=min(ret,s[i]);	return ret;}void test(int a,int b){	int c=z(v[b]-v[a]);	a++,b++,minn=min(minn,c);	if(query(b)<=c)	return ;	updata(b,c);	to[cnt]=a,val[cnt]=c,next[cnt]=head[b],head[b]=cnt++;}int main(){	//freopen("bz4168.in","r",stdin);	n=rd(),m=rd(),B=ceil(sqrt(n));	int i,j,k,last;	for(i=0;i<n;i++)	v[i]=rd();	memset(cls,0x3f,sizeof(cls));	memset(s,0x3f,sizeof(s));	for(i=0;i<n;i+=B)	{		for(j=i;j<i+B&&j<n;j++)	p[v[j]]=1;		for(last=-1<<30,j=1;j<=n;j++)	cls[i/B][j]=min(cls[i/B][j],j-last),last=p[j]?j:last;		for(last=1<<30,j=n;j>=1;j--)	cls[i/B][j]=min(cls[i/B][j],last-j),last=p[j]?j:last;		for(j=i;j<i+B&&j<n;j++)	p[v[j]]=0;	}	memset(head,-1,sizeof(head));	for(i=n-1;i>=0;i--)	{		minn=1<<30;		for(j=i+1;j<i/B*B+B&&j<n;j++)	if(v[j]!=v[i]&&z(v[j]-v[i])<minn)	test(i,j);		for(j=i/B+1;j*B<n;j++)	if(cls[j][v[i]]<minn)	for(k=j*B;k<j*B+B&&k<n;k++)	if(v[k]!=v[i]&&z(v[k]-v[i])<minn)	test(i,k);	}	for(k=1;k<=m;k++)	{		for(i=0;i<=n;i++)	f[k&1][i]=1<<30;		for(i=1;i<=n;i++)		{			f[k&1][i]=f[k&1][i-1];			for(j=head[i];j!=-1;j=next[j])	f[k&1][i]=min(f[(k&1)^1][to[j]-1]+val[j],f[k&1][i]);		}	}	printf("%d\n",f[m&1][n]);	return 0;}

【BZOJ4167】永远的竹笋采摘 分块+树状数组