题解 [ZJOI2010] 基站选址

Description

有 N 个村庄坐落在一条直线上，第 i(i>1) 个村庄距离第 1个村庄的距离为 $$D_i$$。需要在这些村庄中建立不超过 K个通讯基站，在第 i个村庄建立基站的费用为 $$C_i$$。如果在距离第 i 个村庄不超过 $$S_i$$ 的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第 i 个村庄没有被覆盖，则需要向他们补偿，费用为 $$W_i$$。现在的问题是，选择基站的位置，使得总费用最小。

设$f[i][j]$表示前i个村庄建立j个基站，第i个强制选的最小价值。

经过一番考虑，我们容易得到一下的DP方程：

$f[i][j]=\min_{k\in[1,i-1]}\{f[k][j-1]+cost(k,i)\}+c[i]$

其中$cost(k,i)$表示\sum_{D_k<D_p-S_p\and D_i>D_p+S_p}W[p]。

时间复杂度$O(n^2k)$。

发现j这一维只有j-1有关，可以提出到外面，分层进行dp，类似01背包。

瓶颈在于如何计算$cost(k,i)$。

规约：$L[i]$表示能够覆盖到i的左端点，$R[i]$表示能够覆盖到i的右端点。

$L[i],R[i]$可以通过二分第一个大于等于（小于等于）$S_i+D_i$的数。

我们知道，随着i的右移，左边的某些基站便不再能覆盖当前的i。

也就是说每次i有移动，那么$[1,L[i]-1]$里面的f值肯定要加上$W_i$。

对于每次f[i]的转移，可以不用枚举，若是能查询到$[1,i-1]$中f的最小值，那么便可以直接转移。

实现上述操作，区间查询&区间加，我们可以采用线段树来维护。

这样能够做到$O(nk\log n)$。

而对于维护i移动后哪些点会收到影响，也就是维护i是哪些点的R值，我们可以采取邻接表。

因为只要i移动，那些点对于后来的i，肯定要付出$W_i$代价。

而邻接表有效的节省了空间，同样便于插入。

最后补一张图

()

（P.S. 线段树可以重复利用，每个j决策更新一遍）

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
#define ls (x<<1)
#define rs (x<<1|1)
const int N=20009,INF=0x3f3f3f3f;
int n,k,d[N],s[N],w[N],c[N],f[N],L[N],R[N],ans,sum;
int nxt[N<<2],ver[N<<2],h[N],tot;
struct Segment_Tree 
{
	int tag,val;
} tr[N<<2];

inline void add(int x,int y)
{
	ver[++tot]=y,nxt[tot]=h[x],h[x]=tot;
}

inline void build(int x,int l,int r)
{
	tr[x].tag=0;
	if(l==r)
	{
		// tr[x].tag=0;
		tr[x].val=f[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	tr[x].val=min(tr[ls].val,tr[rs].val);
}

inline void down(int x,int l,int r)
{
	int c=tr[x].tag;
	tr[ls].tag+=c;
	tr[rs].tag+=c;
	tr[ls].val+=c;
	tr[rs].val+=c;
	tr[x].tag=0;
}

inline int query(int x,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return tr[x].val;
	int mid=(l+r)>>1,res=INF;
	if(tr[x].tag) down(x,l,r);
	if(L<=mid) res=min(res,query(ls,l,mid,L,R));
	if(R>mid) res=min(res,query(rs,mid+1,r,L,R));
	return res;
}

inline void change(int x,int l,int r,int L,int R,int c)
{
	if(L<=l&&r<=R)
	{
		tr[x].tag+=c;
		tr[x].val+=c;
		return;
	}
	int mid=(l+r)>>1;
	if(tr[x].tag) down(x,l,r);
	if(L<=mid) change(ls,l,mid,L,R,c);
	if(R>mid) change(rs,mid+1,r,L,R,c);
	tr[x].val=min(tr[ls].val,tr[rs].val);
}

signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=2;i<=n;i++) scanf("%lld",&d[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&s[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&w[i]);
	k++,n++;
	d[n]=w[n]=INF;
	s[n]=c[n]=0;
	for(int i=1;i<=n;i++)
	{
		L[i]=lower_bound(d+1,d+1+n,d[i]-s[i])-d;
		R[i]=lower_bound(d+1,d+1+n,d[i]+s[i])-d;
		if(d[R[i]]>d[i]+s[i]) R[i]--;
		// if(i==n) printf("%lld\n",R[n]);
		add(R[i],i);
	}
	// printf("%d %d\n",L[n],R[n]);
	for(int i=1;i<=n;i++)
	{
		f[i]=sum+c[i];//记f[i]为强制选i建基站所最小价值
		for(int j=h[i];j;j=nxt[j])
		{
			sum+=w[ver[j]];	
		}//sum进行累加
	}
	ans=f[n];
	// for(int i=1;i<=n;i++) printf("%d ",f[i]);
	for(int j=2;j<=k;j++)
	{
		build(1,1,n);//每次重新建树
		for(int i=1;i<=n;i++)
		{
			// puts("DEBUG");
			if(i>1) f[i]=query(1,1,n,1,i-1)+c[i];
			else f[i]=INF;
			for(int u=h[i];u;u=nxt[u])
			{
				int v=ver[u];
				if(L[v]>1) change(1,1,n,1,L[v]-1,w[v]);
			}
		}
		ans=min(ans,f[n]);
		// printf("%d\n",f[n]);
	}
	printf("%lld",ans);
	return 0;
}