首先，請注意 \(Slope Trick\) 可不是斜率優化，是一種通過維護斜率序列的優化，它是有一定范圍限制的：

• 連續。
• 是分段一次函數。
• 是凸函數。
• 每一段的斜率較小（通常為 \(O(n)\)），且均為整數。

我們發現如果此上類型的函數相加之后還是上面的一種函數。

它通常用來維護 \(DP\)，維護滿足以上條件的函數的斜率加減來將函數平移，翻轉，相加， 取前綴/后綴 \(min\), 求 \(min,argmin\)， 維護方法如下：

可以先維護在某個 \(x_0\) 處的 \(f(x_0)\),\(k_0\) 以及函數每個斜率變化點的集合。具體地，如果函數在 \(x\) 位置斜率增加了 \(\Delta_k\)，就在集合中插入 \(\Delta_k\) 個 \(x\)。

對于相加：將 \(f(x_0)\),\(k_0\) 直接相加，斜率變化點的集合直接合并。常用于加一次函數、絕對值函數。
對于取前綴/后綴 \(min\)：去掉 \(k >0\ or\ k < 0\) 的部分。
對于求 \(min,argmin\)： 提取 \(k = 0\) 的部分
對于平移：維護 \(f(x_0)\),\(k_0\) 的變化,斜率變化點在全局打平移標記。
對于翻轉：維護 \(f(x_0)\),\(k_0\) 的變化,斜率變化點在全局打翻轉標記。

例題

# P4597 序列 sequence 以及 # CF13C Sequence，# CF713C Sonya and Problem Wihtout a Legend，# P2893 [USACO08FEB] Making the Grade G 其實是一道題啦。

先讓我去打一下，還沒打QwQ

嗨嗨嗨，打完啦，其實就是一道題。。。

由于數據范圍問題，我們只講# P4597 序列 sequence 以及 # CF13C Sequence，# CF713C Sonya and Problem Wihtout a Legend

我們先考慮樸素的方法， 定義 \(f_{i,j}\) 為考慮 \(1 ~i\) 能滿足是非降數列且最后一個數是 \(j\) 的最小花費。
則有 \(f_{i,j} = \min_{k \le j}\{f_{i-1,k} + |j - a_i|\}\) ,但是這是過不去的， ~但是# P2893 [USACO08FEB] Making the Grade G 是能過滴~。注意到只要設 \(g_i(j) = f_{i,j}\) 發現這 \(g_i\) 是滿足 \(Slope Trick\) 的函數的條件！用因為 \(g_i\) 就是 \(g_{i - 1}\) 先取前綴再取 \(\min\) 得到的，顯然用 \(Slope Trick\)呀！就做完了，按上面做就行了！

代碼如下：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 10;

int n;
int a[N];
priority_queue<int> heap;
int ans;

signed main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    for(int i = 1 ; i <= n ; i ++ )
    {
        if(heap.size() == 0)
        {
            heap.push(a[i]);
            continue;
        }
        if(heap.top() > a[i])
        {
            ans += (heap.top() - a[i]);
            heap.pop();
            heap.push(a[i]);
        }
        heap.push(a[i]);
    }
    cout << ans;
    return 0;
}

其實還有兩道例題的，但是它是 # P3642 [APIO2016] 煙花表演 和# CF1787H Codeforces Scoreboard有點難慢慢啃 \(QwQ\).