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