- p2605 线段树优化转移DP
- 我们很显然可以想到的是定义 \(f_{i,j}\) 表示到 \(i\) 为止 \(i\) 为通讯基站，总共建了 \(j\) 个通讯基站的最小代价
- 那么我们可以得到转移方程
- \(f_{i,j} = \min(f_{k,j-1} + w_{i,k}) + c_i\)
- 其中 \(w_{i,k}\) 表示 \(k - i\) 之间需要补偿的总费用
- 对于一个在 \(k - i\) 之间的基站 \(x\) 来言，如果 \(i > x + s_x\) 且 \(k < x - s_i\) 那么就需要补偿
- 我们可以很轻松的发现 \(j\) 的枚举可以放在外围
- 那么我们可以将每一个 \(x\) 的 \(x + s_x + 1\) 打上标记 \(x\)
- 当我们遍历到 \(i\) 的时候在线段树上的区间 \([1,x-s_x-1]\) 打上加 \(w_x\) 的标记
- 再求出 \([1,i-1]\) 区间的最小值更新即可
- 为什么我没有想到
- 方程转移式列对了
- 但在考虑如何优化转移的时候想歪了
- 没有想到 \(j\) 的枚举可以放在外围
- 转移只和第二维的 \(j-1\) 有关时可以考虑把 \(j\) 的枚举放在最外围
- 然后想了 \(w_{i,k}\) 是否具有单调性？
- 但是它是具有但不是固定的，但是很显然可以发现任意的 \(f_t <= f_{t+1}\) 所以完全没有意义
- 所以说思路到这里就全断了
- 稍微看了一眼题解发现自己真的是糖丸了
- 有时候可以考虑元素对转移的贡献，而不是转移本身
