# Aliens 優化
###### tags: `Competitive Programming Note`

本文已停止更新，新版請至 [WiwiHo 的競程筆記](https://cp.wiwiho.me/)

Aliens 優化是 DP 優化的一種，先看例題：[AI-666 賺多少](https://zerojudge.tw/ShowProblem?problemid=c457)，雖然這題有 Greedy 的作法，但我們要用 Aliens 優化來做。

先想想看如果沒有交易次數的限制可以怎麼做，令 $dp_0[i]$ 是到第 $i$ 個時間點結束時，手上沒有商品的最大獲利，而 $dp_1[i]$ 是手上有商品的最大獲利，$a[i]$ 是時間點 $i$ 時商品的價格，然後可以很簡單地得到轉移式：
$$\begin{align*}
dp_0[i] &= \max(dp_0[i - 1], dp_1[i - 1] + a[i]) \\
dp_1[i] &= \max(dp_1[i - 1], dp_0[i - 1] - a[i])
\end{align*}$$
答案就是 $dp_0[N]$，算這個的同時也可以得到最大獲利需要的最少交易次數是多少。用相似的作法再加上一個維度，就可以算在交易次數限制下的最大獲利了，不過那樣的時間複雜度是 $O(NK)$，所以我們不會這樣做。

令 $f(k)$ 是做恰 $k$ 次交易時的最大獲利，雖然我們不能很快地算出 $f(k)$，但我們可以用 $O(N)$ 的時間算出 $\max\{f(k)\}$ 和得到極值發生的 $k$，也就是最大獲利和需要的交易次數。先知道這件事，待會會用到。

$f(k)$ 有一個重要的性質是，它是一個凹函數（concave function），凹函數的意思是這個函數的切線斜率也就是差分（我們都在整數上做事）非嚴格遞減，用直覺的方式說明一下就是如果 $f(k-1) - f(k-2) < f(k) - f(k-1)$，也就是 $f(k)$ 多做的那次獲利比 $f(k-1)$ 多做的那次多，那麼我乾脆把 $f(k-1)$ 多做的那次交易換成 $f(k)$ 多做的那次，所以多出來的獲利一定會越來越少。

那麼凹函數可以幹嘛呢？我們要做一件神奇的事情，就是對每次交易多收 $p$ 元的手續費，令得到的新函數是 $f'(k)=f(k)-kp$，而 $f'(k)$ 也會是凹函數，因為：
$$f'(k)-f'(k-1)=(f(k)-kp) - (f(k - 1)-(k-1)p)=f(k)-f(k-1)-p$$
所以就只是 $f(k)$ 的差分全部減去 $p$ 而已，差分遞減這件事不會改變。

要計算 $\max\{f(k)-kp\}$ 和極值發生的 $k$ 很簡單，只要修改一下轉移式：
$$dp_1[i] = \max(dp_1[i - 1], dp_0[i - 1] - a[i] - p)$$
同樣可以 $O(N)$ 算出來。

接下來注意到一件事：對於一個凹函數，它的極值發生點就是第一個 $f'(k+1)-f'(k) \leq 0$ 的 $k$，而「把差分全部減去 $p$」就會改變這個位置，然後我們又可以輕鬆算出來極值和它的位置，還有顯然 $p$ 越大，極值就會在越左邊的地方，因此我們可以二分搜 $p$（為了實作方便，**我們讓這個 $p$ 是最小的那一個**，它會等於 $f(k+1)-f(k)$，讓 $f'(k+1)-f'(k)$ 剛好變 0），讓極值發生在我們想要的 $K$，就可以得到 $f(K)-Kp$，把 $Kp$ 加回去就是答案了。（這題有一個要特別注意的地方是如果本來極值位置就 $\leq K$，要直接輸出答案。）

示意圖，藍色是 $f'(k)$，紅色是 $f'(k+1)-f'(k)$，金色是極值的位置：
<!-- source code: https://gist.github.com/wiwiho/40e5a7969a3f827e0d95a47db5f833a9 -->

有一個特殊狀況是，因為我們是找「最大獲益需要的最少交易次數」，也就是最左邊的極值位置，而在 $f(K)-f(K-1)=f(K+1)-f(K)$，也就是 $f(K-1),f(K),f(K+1)$ 等差時，$K$ 永遠不會是差分第一個變成 $\leq 0$ 的點，也就不會是最左邊的極值位置。在這個時候，如果直接二分搜的話，會得到一個 $t$ 滿足
$$p=f(t+1)-f(t)=f(t+2)-f(t+1)=...=f(K)-f(K-1)=f(K+1)-f(K)$$
也就是 $t$ 到 $K$ 會是一條直線，且 $t$ 是整條等差的最左邊那個點，可以推得：
$$\begin{align*}
&f'(t+1)-f'(t)=...=f'(K+1)-f'(K) \\
=&f(t+1)-f(t)-p=...=f(K+1)-f(K)-p \\
=&p-p=0
\end{align*}$$
也就是 $f'(t)=f'(t+1)=...=f'(K)$，因此 $f'(t)+Kp=f'(K)+Kp$，直接加 $Kp$ 也會是好的，結論就是完全不用理會這個狀況。

至於二分搜的上下界呢？因為我們希望最後找到 $p=f(K+1)-f(K)$，所以這個數字一定要在二分搜的範圍裡，因此二分搜範圍就和差分的範圍一樣。~~如果不會算的話也可以隨便開一個很大的範圍，反正二分搜很快，TLE 再縮小就好。~~

時間複雜度是 $O(N \log C)$，比 $O(NK)$ 好多了。

## 總結

Aliens 優化就是用這種「移動極值」的想法，來把本來要多開一個維度的事用二分搜做掉。如果用互動題來講，會像是這樣：

> 有一個凹函數 $f(k)$，你不知道它長什麼樣子，但是你可以把一個數字 $p$ 丟進一台機器裡，它會告訴你最大的 $f(k)-kp$ 是多少，以及讓這個值最大的 $k$ 為何，求 $f(K)$。

除了凹函數可以用以外，凸函數（差分非嚴格遞增的函數）也可以用 Aliens 優化做，因為它和凹函數同樣有差分具單調性的特性，這樣的題目會變成是求最小值，而極值發生的位置變成第一個 $f(k+1)-f(k) \geq 0$ 的地方，還有 $f(k)-kp$ 要換成 $f(k)+kp$（這樣才不用改太多東西 (?)），就是想成它是一個凹函數倒過來就好了。

:::warning
如果 $p$ 可能是負數，二分搜的時候注意除法會向零取整。
:::

### 實作細節

實作就二分搜而已，但有一件特別重要的事情是 $p$ 是要找最小那一個，在這個時候我們一定會找到 $p=f(K+1)-f(K)$，剛剛我們都是以這件事為前提做事的，現在來仔細分析一下不這樣做會怎樣。

我們的主要目標是「找到 $p$ 使得 $f(k)-kp$ 的極值在 $K$」，在 $f(K)-f(K-1) \neq f(K+1) - f(K)$ 時，而這個 $p$ 的範圍可以是 $[f(K+1)-f(K), f(K)-f(K-1))$ 中的任何一個數，在這種時候無論我們找到的 $p$ 是多少，只要落在這個範圍就會是好的，因為極值一定在 $K$。

而當 $f(K)-f(K-1) = f(K+1) - f(K)$ 就會發生前面有提到的，$K$ 不可能是極值位置的狀況發生，這個時候，如果你的二分搜長這樣：

while(l < r){
    int m = (l + r + 1) / 2;
    if(calc(m) >= K) l = m; // calc(p) = f(k)-kp 的最左邊極值位置
    else r = m - 1;
}

也就是你試圖去找到最大的好的 $p$，而不是最小的，這樣你其實會得到 $p=f(K+1)-f(K)-1$，因為一旦 $p \geq f(K+1)-f(K)$，極值位置就會跑到 $K$ 的左邊去，這樣子 $f'(K+1)-f(K)$ 會是 1，且得到的極值位置會是整條等差最右邊那個點，跟我們剛剛想要的 $f'(K+1)-f(K)=0$ 完全不一樣，直接加 $Kp$ 回去也會是錯的。

所以二分搜要長這樣才對：

while(l < r){
    int m = (l + r) / 2;
    if(calc(m) <= K) r = m;
    else l = m + 1;
}

其實也不是一定要這樣，如果你拿上面兩份程式碼各跑一次，會得到兩個 $p$，假設找最小版是 $p_1$、找最大版是 $p_2$，而得到的極值位置會在整條等差的最左和右邊，假設是 $v_1$ 和 $v_2$，你可以得到 $f(v_1)$ 和 $f(v_2)$，反正它們兩個之間等差且 $K$ 在中間，那就用它們算出 $f(K)$ 就好：
$$f(K)=f(v_1)+\frac{f(v_2)-f(v_1)}{v_2-v_1} \times (K- v_1)$$
但是直接加 $Kp$ 的作法顯然輕鬆許多，所以就好好找最小的 $p$ 吧。