LuoguP2605 [ZJOI2010]基站选址 题解

(Updated: )
oi
,

Description

题目链接

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

求出最小的总费用。

$1\leq N \leq 2\times 10^4,1\leq K \leq 100$。

Solution

首先很容易就可以列出一个暴力 $DP$ 方程：

设 $dp[i][j]$ 表示前 $i$ 个村庄，造 $j$ 个通讯基站的最小花费。

$$dp[i][j]=\min\{dp[k][j-1]+cost[k,i]\}+C_i$$

很显然，这题的瓶颈主要在求解 $cost[k,i]$ 上。

我们可以令 $st[i]$ 表示如果在村庄 $i$ 造基站，向左最多能覆盖到哪个村庄，$ed[i]$ 表示向右最多能覆盖到哪个村庄。

考虑用线段树维护下 $\min\{dp[k][j-1]+cost[k,i]\}$

我们每次更新 $dp[i][j]$ 时，可以把 $ed[k]$ 刚好为 $i$ 的 $k$ 的 $[1,st[k]-1]$ 的 $cost$ 全部加上 $w[k]$（代表这些村庄需要补偿）。

因为所有后面的点，如果要从 $[1,st[k]-1]$ 的点转移过来，$k$ 必定无法被覆盖到，所以要加上赔偿费用。

然后更新的时候直接取用 $[1,j-1]$ 的最小值即可。

最后可以在无穷远处开个费用为 $0$ 的点，便于统计答案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=20010;
int n,m,d[N],c[N],s[N],w[N],inf=2e9,f[N],tr[N<<2],tag[N<<2],st[N],ed[N];
vector<int> v[N];
#define IT vector<int>::iterator
#define LW(x) lower_bound(d+1,d+n+1,x)-d
#define mid (l+r>>1)
#define ls x<<1,l,mid
#define rs x<<11,mid+1,r
#define UP(x) tr[x]=min(tr[x<<1],tr[x<<11])
#define PD(x) tag[x]&&(Add(x<<1,tag[x]),Add(x<<11,tag[x]),tag[x]=0)
IT It;
I void Add(CI x,CI val){tr[x]+=val;tag[x]+=val;return ;}
I void build(CI x,CI l,CI r){if(tag[x]=0,l==r) return void(tr[x]=f[l]);build(ls),build(rs),UP(x);}
I void update(CI x,CI l,CI r,CI L,CI R,CI val){if(L>R) return ;if(L<=l&&r<=R) return Add(x,val);PD(x);if(L<=mid) update(ls,L,R,val);if(R>mid) update(rs,L,R,val);UP(x);}
I int query(CI x,CI l,CI r,CI L,CI R){if(L>R) return inf;if(L<=l&&r<=R) return tr[x];PD(x);RI res=inf;if(L<=mid) res=min(res,query(ls,L,R));if(R>mid) res=min(res,query(rs,L,R));return res;}
int main(){
RI i,j,S;read(n,m);for(d[1]=0,i=2;i<=n;i++) read(d[i]);for(i=1;i<=n;i++) read(c[i]);for(i=1;i<=n;i++) read(s[i]);for(i=1;i<=n;i++) read(w[i]);++m,++n,d[n]=w[n]=inf;
for(i=1;i<=n;i++) st[i]=LW(d[i]-s[i]),ed[i]=LW(d[i]+s[i]),d[ed[i]]>d[i]+s[i]&&ed[i]--,v[ed[i]].push_back(i);for(S=0,i=1;i<=n;i++) for(f[i]=S+c[i],It=v[i].begin();It!=v[i].end();It++) S+=w[*It];
for(S=f[n],i=2;i<=m;S=min(S,f[n]),i++) for(build(1,1,n),j=1;j<=n;j++) for(f[j]=query(1,1,n,1,j-1)+c[j],It=v[j].begin();It!=v[j].end();It++) update(1,1,n,1,st[*It]-1,w[*It]);return writeln(S),0;
}