LuoguP2605 [ZJOI2010]基站选址 题解

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

#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<<1|1,mid+1,r
#define UP(x) tr[x]=min(tr[x<<1],tr[x<<1|1])
#define PD(x) tag[x]&&(Add(x<<1,tag[x]),Add(x<<1|1,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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇