【BZOJ1835】基站选址（线段树）

时间：2022-10-11 12:47:39

【BZOJ1835】基站选址（线段树）

题面

BZOJ

题解

考虑一个比较暴力的\(dp\)

设\(f[i][j]\)表示建了\(i\)个基站，最后一个的位置是\(j\)的最小代价

考虑如何转移\(f[i][j]=min(f[i-1][p]+Cost(p+1,j)+C[j])\)

其中\(Cost\)表示代价，也就是区间内所有没有被覆盖的村庄的\(W\)的和

如果直接暴力\(dp\)，复杂度\(O(n^2k)\)，这个复杂度还假设了\(Cost\)是\(O(1)\)计算的

转移的时候是枚举建造的个数，显然还可以滚调第一维

但是这个复杂度我们无法接受，我们要思考有没有更快的方法

考虑\(dp\)的转移式子

\(f[i][j]=min(f[i-1][p]+Cost(p+1,j)+C[j])\)

\(f[i][j]=min(f[i-1][p]+Cost(p+1,j))+C[j]\)

相当于我们要找到的就是\(min(f[i-1][p]+Cost(p+1,j))\)

我们不难知道，如果一个村庄不需要贡献他的\(W\)

那么，必须在一个区间内存在一个基站

所以，这个区间我们可以提前预处理出来（二分一下）

然后按照右端点排序，按照右端点结束的位置分类

从左到右这样扫过来，如果过了某个右端点

此时，这些区间的最右端在当前位置的那些村落，

在后面的\(dp\)中必然产生贡献，

会对\([1,left-1]\)的所有区间都产生\(W\)的贡献

因此在线段树上做一次区间加法

每次进行转移的时候从所有的位置中选出区间最小值就行了

然后\(K\)增大，重构线段树即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define RG register

#define ll long long

#define MAX 30000

#define lson (now<<1)

#define rson (now<<1|1)

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int f[MAX];

struct Node{int v,tag;}t[MAX<<2];

struct Seg{int l,r;}p[MAX];

vector<int> V[MAX];

int n,K,W[MAX],S[MAX],d[MAX],C[MAX],ans=2e9;

void Build(int now,int l,int r)

{

	t[now].tag=0;

	if(l==r){t[now].v=f[l];return;}

	int mid=(l+r)>>1;

	Build(lson,l,mid);Build(rson,mid+1,r);

	t[now].v=min(t[lson].v,t[rson].v);

}

void puttag(int now,int w){t[now].v+=w;t[now].tag+=w;}

void pushdown(int now)

{

	puttag(lson,t[now].tag);

	puttag(rson,t[now].tag);

	t[now].tag=0;

}

void Modify(int now,int l,int r,int L,int R,int w)

{

	if(L>R)return;

	if(L<=l&&r<=R){puttag(now,w);return;}

	pushdown(now);

	int mid=(l+r)>>1;

	if(L<=mid)Modify(lson,l,mid,L,R,w);

	if(R>mid)Modify(rson,mid+1,r,L,R,w);

	t[now].v=min(t[lson].v,t[rson].v);

}

int Query(int now,int l,int r,int L,int R)

{

	if(L>R)return 0;

	if(L<=l&&r<=R)return t[now].v;

	pushdown(now);

	int mid=(l+r)>>1,ret=2e9;

	if(L<=mid)ret=min(ret,Query(lson,l,mid,L,R));

	if(R>mid)ret=min(ret,Query(rson,mid+1,r,L,R));

	return ret;

}

int main()

{

	n=read();K=read();

	for(int i=2;i<=n;++i)d[i]=read();

	for(int i=1;i<=n;++i)C[i]=read();

	for(int i=1;i<=n;++i)S[i]=read();

	for(int i=1;i<=n;++i)W[i]=read();

	for(int i=1,l,r,pos;i<=n;++i)

	{

		l=1,r=i-1,pos=i;

		while(l<=r)

		{

			int mid=(l+r)>>1;

			if(d[i]-d[mid]>S[i])l=mid+1;

			else pos=mid,r=mid-1;

		}

		p[i].l=pos;

		l=i+1,r=n,pos=i;

		while(l<=r)

		{

			int mid=(l+r)>>1;

			if(d[mid]-d[i]>S[i])r=mid-1;

			else pos=mid,l=mid+1;

		}

		p[i].r=pos;

	}

	for(int i=1;i<=n;++i)

		V[p[i].r].push_back(i);

	for(int i=1,tmp=0;i<=n+1;++i)

	{

		f[i]=tmp+C[i];

		for(int j=0;j<V[i].size();++j)

			tmp+=W[V[i][j]];

	}

	ans=f[n+1];

	for(int i=1;i<=K;++i)

	{

		Build(1,1,n+1);

		for(int j=1;j<=n+1;++j)

		{

			f[j]=Query(1,1,n+1,1,j-1)+C[j];

			for(int k=0;k<V[j].size();++k)

				Modify(1,1,n+1,1,p[V[j][k]].l-1,W[V[j][k]]);

		}

		ans=min(ans,f[n+1]);

	}

	printf("%d\n",ans);

	return 0;

}

相关文章