首页 > 题解 > bzoj 1835 [ZJOI2010]基站选址

bzoj 1835 [ZJOI2010]基站选址

题目描述

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

输入输出格式

输入格式:

输入文件的第一行包含两个整数N,K,含义如上所述。

第二行包含N-1个整数,分别表示D2,D3,…,DN ,这N-1个数是递增的。

第三行包含N个整数,表示C1,C2,…CN。

第四行包含N个整数,表示S1,S2,…,SN。

第五行包含N个整数,表示W1,W2,…,WN。

输出格式:

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

输入输出样例

输入样例#1:

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

输出样例#1:

4

说明

40%的数据中,N<=500;

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

题解:

动态规划+线段树优化的一道好题

以下设c[i]是i村庄建立基站的费用,w[i]是i村庄没被覆盖的补偿费用

定义状态

$f(i,j)$表示前j个村子建立了i个基站且第i个基站建立于j号村子的费用(包括前j个村的建站费和补偿费)

先写出朴素DP的方程:$f(i,j)=min \{ f(i-1,k)+cost(k,j) \} +c(j)$,其中$1<=k<=j-1$,$cost(k,j)$是只在k和j两点修建基站,对于两点中间村庄的补偿费用

其中第i层的状态只和第i-1层相关,可以降维成$f(i)=min \{ f(j)+cost(j,i) \} +c(i),1<=j<=i-1$

可是我们发现,计算$cost(j,i)$是一个$O(n^3)$的过程,效率过低

那么现在的问题就是如何维护$cost$

优化

我们假设$f(j)$目前已经计算完了,现在想要计算$f(j+1)$

我们转移每一层$(1 \sim K)$时,建立一棵线段树,对于每个点k维护$f(k)+cost(k,j)$(注意这个东西是随着j的增长而变化的)

观察一下方程,可以发现,原方程中每个$f(k),1<=k<=j-1$是不随着j的增长而变化的,变化的只有$cost(k,i)$

是什么引起了$cost(k,i)$的变化呢?从$cost(k,i)$变化到$cost(k,i+1)$,说明有些本来能被i位置建立的一座基站覆盖到的村子,因为$i->i+1$而覆盖不到了,需要给他们补偿

那么我们可以预处理出每个村庄的$l$和$r$,分别代表在村庄i左(右)侧建立基站仍能覆盖到村庄i的最远村庄位置,这个可以二分求出,$O(nlogn)$

每次转移完$f(i)$时,将$r(x)=i$的所有x,将$[1,l[x]-1]$这段区间在线段树中加上$w[x]$即可

细节处理

实际实现的时候我们发现每层的答案并不一定是$f(n)$,因为最后一个基站不一定建立在最后一个村庄

那么我们开始的时候$++n$和$++K$,在最后添加一个距离正无穷,建站费用为0,补偿费用为正无穷的村子

这样之后$f(n)$就一定是答案了


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×