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

暂无评论

发送评论 编辑评论


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