---
tags: 資訊,資訊講義
---

# DP斜率優化I

最近終於大概弄懂斜率優化到底是什麼了
花了好久的時間弄懂

這篇主要是在講查詢單調&斜率單調的斜率優化
所以沒有動態凸包&李超線段樹(因為這兩個我都不會)

## 斜率優化簡介

斜率優化的dp式大概長這樣

$$dp[i] = \mathop{min}\limits_{j<i}(a[j] * x[i] + b[j] ) + c[i]$$

基本上這一看就知道這是1D1D的DP轉移式
很容易就寫得出$O(n^2)$的code

但是這樣太慢了，所以我們就要針對這個DP式的特性來優化，$min$中間的$a[j] * x[i] + b[j]$有沒有長的很像一條直線，所以我們可以利用這個特性來做一些改變。

## 斜率優化數學性質

### query的時候

### 查詢單調
假設$i$是遞增、有兩條線段的話，我們可以畫出兩條直線，其中綠色的斜率比較大，藍色的斜率比較小。


當我們在詢問的時候，發現 $a$ 點比 $b$ 點對應的值來的低，正因為有個假設前提，$i$是遞增，所以綠色那條在之後的詢問就絕對不是答案，就可以把綠色的那條給移除掉，留下藍色那一條。

### 查詢不單調
那如果查詢不單調時怎麼辦？
就直接二分搜阿(?

### insert的時候

因為斜率是遞增的，所以插入直線時只會有兩種狀況。

一個是在藍色與綠色交點的右側，一個是在左側。
此時我們把最低點都畫出來(橘色線是當前最低點)

我們發現交點在右側時，每一條線都可能會是最低點，但在左側時，藍色這一條就永遠不會是最低點。所以我們可以把藍色那一條給移除掉。
如果我們把這些永遠不會是答案的線段移除掉的話，就會形成一個凸包。

上面的狀況都是在答案是最小值，如果是在最大值的話那情況就會相反

## 實作
首先，先宣告一個struct

struct line{
    int a, b;

    int operator() (int x){
        return a * x + b;
    }
};

operator()代表是在x的時候對應的值，這裡有很多種寫法，可以看個人去做更改

bool dot(line a, line b, line c){
    return (b.a - a.a) * (c.b - b.b) <= (b.b - a.b) * (c.a - b.a);
}

假設我們有三個線段
$$ a_1 x + b_1 $$

$$ a_2 x + b_2 $$

$$ a_3 x + b_3 $$

$a_1 x + b_1$代表比較舊的那條線段，$a_2 x + b_2$代表比較新的那條，$a_3 x + b_3$代表要插入的線段。

那我們先求出舊的那條線段與新的那條線段的交點$x_1$
$$ a_1 x_1 + b_1 = a_2 x_1 + b_2 $$

$$ a_1 x_1 -a_2 x_1 = b_2 - b_1$$

$$ (a_1 - a_2) x_1 = b_2 - b_1$$

$$ x_1 = \frac{b_2 - b_1}{a_1 - a_2}$$

再求出新的那條與要插入的線段的交點$x_2$，方法跟上面一樣。因為我們要求的是最小值，所以如果新的線段要被包圍的話，$x_2$就必須大於等於$x_1$

$$ x_2 \geq x_1 $$

那展開就會變成這樣

$$ \frac{b_2 - b_3}{a_3 - a_2} \geq \frac{b_2 - b_1}{a_1 - a_2}$$

那這樣就可以得到三線的交點狀況了。
其實這邊也可以只用除法，但是除法本身會有精度問題，再加上可能會發生除0的狀況，所以建議還是用乘法會比較好。

void insert(line a){
    while (dq.size() >= 2 && dot(dq[dq.size() - 2], dq[dq.size() - 1], a))
        dq.pop_back();

    dq.push_back(a);
}

insert的想法在上面的數學性質有，就是判斷三條線的交點狀況而已。

int query(int x){
    while (dq.size() >= 2 && dq[0](x) >= dq[1](x))
        dq.pop_front();
    return dq[0](x);
}

query的想法也是在上面的數學性質裡有，複雜度是$O(1)$，但要注意的的是這個query的x只能遞增，簡單來講就是查詢要有單調性。

int query2(int x){
    int l = -1, r = dq.size();
    while (r - l > 1){
        int m = (l + r) >> 1;
        if (dq[m](x) >= dq[m + 1](x)) l = m;
        else r = m;
    }
    return dq[r](x);
}

這個query一看就知道是二分搜，時間複雜度是$O(logn)$，可以用在查詢不單調上。

## atcoder dp-z frog3

那如果上面的數學性質都看得懂的話就可以來寫這題了(?

我們可以很簡單的就寫出這題的轉移式

$$dp[i] = \mathop{min}\limits_{j<i}(dp[j] + (h[i] - h[j])^2 + c) $$
然後展開&化簡
$$dp[i] = \mathop{min}\limits_{j<i}(dp[j] + h[i]^2 -2h[i]h[j] + h[j]^2 + c) $$

$$dp[i] = \mathop{min}\limits_{j<i}(dp[j] -2h[i]h[j] + h[j]^2 )+ h[i]^2 + c$$

$$dp[i] = \mathop{min}\limits_{j<i}((-2h[j])h[i] + h[j]^2 + dp[j] )+ h[i]^2 + c$$
此時$a = (-2h[j])$ , $b = h[j]^2 + dp[j]$
這樣就可以變成 $ax+b$ 的形式
只要查詢$h[i]$就可以了

### submission
[我的code](https://atcoder.jp/contests/dp/submissions/24162913)

## 後記

這種優化應該是斜率優化裡面最簡單的了，斜率優化還有一些比較難的題目，像是查詢不單調和斜率不單調。

查詢不單調可以用二分搜來解決，但斜率不單調就要用李超&動態凸包之類的來解，這兩個我還在慢慢了解，還不熟QQ，希望今年可以都學到這兩種。