跟风 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}\) 也会增加,决策点前面的点就没有成为新的决策点的机会,那么就是满足决策单调性的。
至于怎么实现,可以用 单调队列
/ 整体二分
来做