# 斜率優化

### 前言
如果斜率有單調性(m[i]<=m[i+1]<=m[i+2])，就看這篇，用deque解決;
如果斜率沒有單調性，就要用[李超線段樹](/Mn69f9ZMRmqxjMOZfURuWg)。

----------------
先看例題 : [Monster Game I](https://cses.fi/problemset/task/2084)
接著我們可以定義dp
$$dp[i]=打第i個怪所需的最小時間$$
轉移式則為
$$
dp[0]=s[0]=0,f[0]=x\\
dp[i]=min\{s[i]×f[j]+dp[j]\}
$$
結論是要在所有小於$i$的$s[i]×f[j]+dp[j]$中找最小值，也就是要把$s[i]$帶進去，看哪個結果最小，就更新dp，假設我們要找的最小值為y，那y會等於 :
$$
y=f[j]×s[i]+dp[j]\\
y=ax+b
$$
其實就是一條直線，因此我們可以想成有$i-1$條直線$y=f(x)$，要帶入$s[i]$求$f(s[i])$的最小值。

我們又可以發現，斜率$f[i]$是有單調性的(遞減)，因此畫在圖上的線長可能這樣 :


當$s[i]$在左半邊時，最小值發生在$L1$上，但到右半邊後，最小值卻變發生在$L3$上，接著來看這張圖 :


最小值依序發生在$L1、L2、L3$，觀察一下可以發現，隨著$x$往右更新($s[i]$有遞增姓)，原本有最小值的斜線會被後面來的斜線追過。

因此我們可以依序把線存起來，等到後面的線帶入$s[i]$的值<前面的線帶入$s[i]$的值，就把前面的線pop出來。

while(q.size()>=2 && q[1].y(s[i])<q[0].y(s[i]))
    q.pop_front();

但是要注意一種情況 :

$L1$和$L3$可以夾殺(讓$L2$沒用)$L2$，這時候如果還是判斷$L2$有沒有小於$L1$的話就會是錯的，因為在黃色區段中，如果$L2$<$L1$就會把L1踢掉，然後再判斷$L2$和$L3$，最終會留下$L3$，但是在黃色區段中$L2$並未<$L1$，所以答案就只會取到$L1$。

**那要怎麼樣才能避免沒用的線導致答案錯誤的情況呢?**
很簡單，那就是在push進去的時候把沒用的刪掉，判斷如果倒數第二條線和當前準備放進去的線能夾殺倒數第一條線的話，就把倒數第一條線pop掉。

**那要怎麼判斷能不能夾殺呢?**
可以用$x$座標來判斷 : 如果$L23$的交點$x$座標比$L12$的交點$x$座標小，就可以夾殺，因為把$L2$當基準線後，加上斜率的遞減性，要用到$L2$一定是$L23$的交點$x$座標比$L21$的交點$x$座標大(也就是上面第二張圖)。

**那交點座標$x$要怎麼求呢?**

$$
L1:y = ax + b \\
L2:y = cx + d \\
~\\
ax + b = cx + d \\
ax - cx = d - b \\
~\\
x = \frac{d - b}{a - c}
$$

int intersection_x(line l1,line l2){  //交點座標x
    return (l2.b-l1.b)/(l1.a-l2.a);
}

bool can_kill(line l1,line l2,line l3){
    int l12=intersection_x(l1,l2);
    int l23=intersection_x(l2,l3);
    return l23<l12;
}

while(q.size()>=2 && can_kill(q[q.size()-2],q[q.size()-1],now)) 
    q.pop_back();

最後還有一點需要注意的是如果遇到跟前面斜率一樣的狀況就不用放進去，不僅是計算$x$交點座標時會變成除以0，還有放進去並不會讓答案更好，因為前一個同斜率的dp值一定比較小(最小值會嚴格遞增)，所以後面線的b(y截距)會比較大，較上面，並不會影響到最小值。

if(q.back().a==now.a) continue;

::: spoiler Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 200005

int s[MAXN],f[MAXN],dp[MAXN];

struct line{
	int a,b;
	int y(int x){
		return a*x+b;
	}
};

int inters(line l1,line l2){
	return (l2.b-l1.b)/(l1.a-l2.a);
}

bool check(line l1,line l2,line l3){
	int l12=inters(l1,l2);
	int l23=inters(l2,l3);
	return l23<l12;
}

signed main(){
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;i++) cin >> s[i];
	for(int i=1;i<=n;i++) cin >> f[i];
	
	deque<line> q;
	q.push_front({k,0});
	
	for(int i=1;i<=n;i++){
		int x=s[i];
		while(q.size()>=2 && q[0].y(x)>q[1].y(x)) q.pop_front();
		dp[i]=q.front().y(x);
		line now={f[i],dp[i]};
		
		if(q.back().a==now.a) continue;
		while(q.size()>=2 && check(q[q.size()-2],q[q.size()-1],now)) q.pop_back();
		q.push_back(now);
	}
	cout << dp[n] << '\n';
}

:::