某岛

… : "…アッカリ~ン . .. . " .. .
October 2, 2014

BZOJ 1835. [ZJOI2010]base 基站选址

Brief description:

x 轴上分布着 n 各村庄,坐标 x_i。在第 i 各村庄,建设基站的费用为 c_i,
。。村庄的【被覆盖半径】为 r_i,表示覆盖 i 村庄的条件是,在 [x_i – r_i, x_i + r_i] 范围内有村庄建设了基站。。
。。每个村庄未被覆盖的惩罚代价是 w_i。。。求建设至多 nn 个基站最小费用。

Brief description:

朴素:
f[ii][i]: 前 i 个村庄,第 ii 个基站建立基站 。。。
f[ii][i] = min(f[ii-1][j] + w(j, i) | ii-1 <= j < i) 这里的代价函数较为复杂: [cpp] int w(int l, int r){ int res = 0; FOR(i, l+1, r) if (l < ll[i] && rr[i] < r) res += _w[i]; return res; } [/cpp] 考察 r 的增加。。只会因为发生 rr[i] == r -> rr[i] < r+1 这样的变化。。而导致代价的增加。。 于是。。我们考虑做一个线段树维护 w(i, j)。。。 。。我们枚举所有 rr[i] = b 的点。 。。将 [0, ll[i]) 这段区间 (也就是满足 l < ll[i])+= _w[i]。。。 http://www.lydsy.com/JudgeOnline/problem.php?id=1835
http://y4612s.logdown.com/posts/189827-solution-bzoj1835-zjoi2010base-base-station-location
https://gist.github.com/lychees/7773b7d7da611f4602e6