【BZOJ1835】[ZJOI2010]base 基站选址线段树+DP

2023-01-10 08:25:28

【BZOJ1835】[ZJOI2010]base 基站选址

Description

有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。输入数据 (base.in) 输入文件的第一行包含两个整数N,K，含义如上所述。第二行包含N-1个整数，分别表示D2,D3,…,DN ，这N-1个数是递增的。第三行包含N个整数，表示C1,C2,…CN。第四行包含N个整数，表示S1,S2,…,SN。第五行包含N个整数，表示W1,W2,…,WN。

Input

输出文件中仅包含一个整数，表示最小的总费用。

Output

3 2 1 2 2 3 2 1 1 0 10 20 30

Sample Input

Sample Output

40%的数据中，N<=500；
100%的数据中，K<=N，K<=100，N<=20,000，Di<=1000000000，Ci<=10000，Si<=1000000000，Wi<=10000。

题解：这题如果想不出来的话，多半是设的状态不对，多设几个可能的状态，很容易就能判断出自己设的状态能否转移了。

设f[i][j]表示在第i个村庄建一个基站，已经建了j个基站，此时前i个村庄需要的最少花费（先不考虑对后面的影响）。那么得到转移方程：

$f[i][j]=f[k][j-1]+C[k]+\sum\limits_{l=k+1}^{i-1}W[l][l既不能被i覆盖也不能被j覆盖]$

那么我们如何求出所有满足条件的W[l]之和呢？为了方便，我们先用二分预处理出对于每个l，能覆盖它的，最左边的村庄（记为lm[l]）和最右边的村庄（记为rm[l]）。那么l不能被k和i覆盖，当且仅当k<lm[l]且rm[l]<i。这就变成了问你一个区间中有多少个线段。我们可以用链表，将所有的l都挂链到rm[l]+1上，那么当i=rm[l]+1时，自然就满足了rm[l]<i的条件。然后我们取出挂在i上的所有l，用线段树，将[1,lm[l]-1]的所有点的f值都+=W[l]，也就对应了k<lm[l]的限制。然后我们直接取出线段树中f最小的k来更新f[i][j]就行了。

请注意DP初值的设定！

#include <cstdio>

#include <cstring>

#include <iostream>

#define lson x<<1

#define rson x<<1|1

using namespace std;

typedef long long ll;

const int maxn=20010;

int n,m,cnt,now,ans;

int D[maxn],W[maxn],C[maxn],S[maxn];

int s[maxn<<4],t[maxn<<4],f[2][maxn],lm[maxn],rm[maxn],to[maxn],next[maxn],head[maxn];

void add(int a,int b)

{

	to[++cnt]=b,next[cnt]=head[a],head[a]=cnt;

}

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;

}

void build(int l,int r,int x)

{

	t[x]=0;

	if(l==r)

	{

		s[x]=f[now][l];

		return ;

	}

	int mid=l+r>>1;

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

	s[x]=min(s[lson],s[rson]);

}

void pushdown(int x)

{

	if(t[x])	s[lson]+=t[x],s[rson]+=t[x],t[lson]+=t[x],t[rson]+=t[x],t[x]=0;

}

void updata(int l,int r,int x,int a,int b,int c)

{

	if(a>b)	return ;

	if(a<=l&&r<=b)

	{

		s[x]+=c,t[x]+=c;

		return ;

	}

	pushdown(x);

	int mid=l+r>>1;

	if(a<=mid)	updata(l,mid,lson,a,b,c);

	if(b>mid)	updata(mid+1,r,rson,a,b,c);

	s[x]=min(s[lson],s[rson]);

}

int query(int l,int r,int x,int a,int b)

{

	if(a<=l&&r<=b)	return s[x];

	pushdown(x);

	int mid=l+r>>1;

	if(b<=mid)	return query(l,mid,lson,a,b);

	if(a>mid)	return query(mid+1,r,rson,a,b);

	return min(query(l,mid,lson,a,b),query(mid+1,r,rson,a,b));

}

int main()

{

	n=rd(),m=rd();

	int i,j,k;

	for(i=2;i<=n;i++)	D[i]=rd();

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

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

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

	int l,r,mid;

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

	{

		l=1,r=i;

		while(l<r)

		{

			mid=l+r>>1;

			if(D[i]-D[mid]<=S[i])	r=mid;

			else	l=mid+1;

		}

		lm[i]=r,l=i+1,r=n+1;

		while(l<r)

		{

			mid=l+r>>1;

			if(D[mid]-D[i]<=S[i])	l=mid+1;

			else	r=mid;

		}

		rm[i]=l-1,add(rm[i]+1,i);

	}

	ans=1<<30;

	memset(f,0x3f,sizeof(f));

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

	for(j=1;j<=m+1;j++)

	{

		build(0,n,1),now^=1;

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

		{

			for(k=head[i];k;k=next[k])	updata(0,n,1,0,lm[to[k]]-1,W[to[k]]);

			f[now][i]=query(0,n,1,0,i-1)+C[i];

		}

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

	}

	printf("%d",ans);

	return 0;

}

码农公寓