「POI2011」Lightning Conductor

跟风 yuzhechuan 写个题解/kk

根据 yuzhechuan 的题解,这个东西其实就在求 \(f_i=\max\limits_{j=1}^n \{ a_j+\sqrt{|i-j|} \}-a_i\),正反取两边即可,改为求 \(f_i=\max\limits_{j=1}^i \{ a_j+\sqrt{i-j} \}-a_i\)

发现这个东西是满足决策单调性的

设 \(i\) 的决策点为 \(j\),发现这个 \(a_j+\sqrt{i-j}\) 其实是随着 \(i\) 的增加而增加的,也就是说如果 \(j\) 是 \(i\) 的决策点的话,那么随着 \(i\) 的增加 \(a_j+\sqrt{i-j}\) 也会增加,决策点前面的点就没有成为新的决策点的机会,那么就是满足决策单调性的。

至于怎么实现,可以用 单调队列 / 整体二分 来做

上一篇:T1 P3515 [POI2011]Lightning Conductor


下一篇:题解 P3527 【[POI2011]MET-Meteors】