Slope Trick

Slope Trick 概念：

$f_i(X)=\min\limits_{Y\leq X}\{f_{i-1}(Y)+abs(Y-a_i)\}$

容易知道上面的 $f_i$ 是一個非遞增函數。這邊定義斜率代表 $f_i(X+1)-f_i(X)$，容易發現斜率是遞減的 ( 因為 $f_{i-1}$ 遞減 )，而斜率最後會降到 $0$。於是我們維護一個集合，這個集合代表讓斜率變化的轉折點。特別的，我們令 $opt(i)$ 代表 $f_i$ 斜率變成 $0$ 的那個轉折點之後的任意點(包含轉折點)，這個點帶進去就是 $f_i$ 的最小值之處。所以我們的目標就是求出 $f_i(opt(i))$。

所以現在我們要做的事情就是快速的求出 $f_i$ 以及好好地維護點集。

假設我們已經把 $f_{i-1}$ 全部求完了。現在我們從在$f_{i-1}$的時候維護的點集下手，我們發現 $a_i$ 這個點，會讓小於 $a_i$ 的點斜率全部 $-1$ (因為大家都會加上 $abs(Y-a_i)$，也就是說前後會差 $1$ )。同理，$a_i$ 以後的所有點斜率會全部 $+1$。所以可以知道 $a_i$ 一定會出現在 $f_i$ 的轉折點點集裡面。

接著我們分兩個 Case 討論：

1.

$opt(i-1)\leq a_i$

$a_i$ 以前全部 $-1$，也就是說 $a_i$ 會是變成 $0$ 的那個轉折點，也就是說 $opt(i)=a_i$。

2.

$opt(i-1)>a_i$

先考慮點集的更新。

因為 $a_i$ 這個點，會讓小於 $a_i$ 的點斜率全部 $-1$ 且 $a_i$ 以後的所有點斜率會全部 $+1$。也就是說 $a_i$ 的出現會讓中間有一個斜率是沒有任何轉折點的，這個時候我們就要放兩個 $a_i$ 進去 (當成兩個轉折點)。

具體來說，如果 $a_i$ 這個點原本在的地方是斜率為 $k$ 的線段，那麼 $a_i$ 以前的線段的斜率變成 $k-1$，而 $a_i$ 以後的斜率變成 $k+1$。此時斜率 $k$ 的轉折點不存在，於是我們用 $a_i$ 來代替。

而此時原本斜率是 $-1$ 的轉折點將會變成斜率是 $0$ 的轉折點。也就是說我們不再需要原本是 $0$ 的轉折點了，所以我們可以把他移除掉。

接下來我們考慮答案的更新：

因為我們有 $f_i(X)=\min\limits_{Y\leq X}\{f_{i-1}(Y)+abs(Y-a_i)\}$。而我們又知道 $opt(i)\leq opt(i-1)$，根據定義，我們知道 $Y=opt(i-1)$ 的時候也會是最小值，所以說 $f_i(opt(i))=f_{i-1}(opt(i-1))+abs(opt(i-1)-a_i)$。

最後我們只要輸出 $f_n(opt(n))$ 就是答案了。

總結：slope trick 簡單來說就是一個維護點集的過程，而在維護點集的時候統計答案。