首页 > 代码库 > 【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】永远的竹笋采摘 分块+树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。