ACMOJ1400. 蓋大樓

題目描述

給定 $\{a_n\}$ ，求 $(a_i+a_j)|i-j|$ 的最大值。

資料範圍

$1 \le n,a_i \le 10^6$

題解

怎麼會有傻瓜想三分呢？怎麼會有傻瓜決策單調總是想不出來呢？

假設選出 $i,j$ ，且 $i<j$ ，那麼 $i$ 左側一定沒有比它大的點，同理， $j$ 右側一定沒有比它小的點。

于是我們可以弄出一個左側單增序列和右側單增序列。然後對于左側的點在右側尋找決策點。（然後猜一下決策單調就過了。）把那個式子變成 $(a_i-(-a_j))|i-j|$ ，在數軸上畫出來就是矩形，然後就很好證明決策單調了。

決策單調用分治實作。

效率： $O(nlogn)$ 。

代碼