浅谈斜率优化

I_LOVE_MATH · 2025-02-07 22:20:10 · 算法·理论

浅谈斜率优化

更好的阅读体验

概论

列出状态转移方程，如果能化简为以下的形式：

此时我们就可以利用单调队列优化从做 O(n^2) 到 O(n) 的复杂度。

现在考虑更一般的情况，如果化简为以下形式：

此时单调队列优化就不再适用，就需要使用斜率优化。

斜率优化的思想就是通过剔除一些不可能成为最优解的决策点，使剩下的决策点形成一个凸包，再使用单调队列、二分、平衡树、CDQ 分治或者李超线段树来快速转移。

理论讲解

斜率优化有两种理解方式：

代数法

设决策点 j_2 优于 j_1。

则有：（< 对应 \max，> 对应 \min）

化简得：

令 Y(x)=-d[x]，X(x)=b[x]，k=a[i]，再让 X(j_2)>X(j_1)。

移项得（不等号要变号）：

这就是说，将两个决策点在平面直角坐标系中用两点表示出来，如果两点间斜率小于（或大于）k，那么后面的点优于前面的点。

现在我们考虑有如下位置关系的三个点：

如图，k_2<k_1。

下面我们讨论 \max 的情况。

• 当 k<k_2<k_1 时，则 C 比 A 优，B 比 C 优，B 最优。
• 当 k_2\le k\le k_1 时，则 A、B 至少有一个比 C 优。
• 当 k_2<k_1<k 时，则 A 比 C 优，C 比 B 优，A 最优。

综上，无论何种情况，C 都不可能最优，可以删去。

推广以上的性质，对于所有的决策点：

删去所有不可能为最优的决策点，发现可能为最优解的点会形成如下的一个下凸包：

同理，对于 \min 的情况，会形成一个上凸包。

几何法

我们先讨论 \max 的情况：

去掉 \max，再移项得：

我们可以将 -d[j] 看作纵坐标，a[i] 看作斜率，b[j] 看作横坐标，c[i]-dp[i]+C 看作常数。

那么此时就可以把状态转移方程看作一个形如 y=kx+b 的直线方程，其中对于同一个 i 斜率 k=a[i] 是不变的。

要使 dp[i] 最大，就要使方程的截距 b 尽可能小。

将所有决策点 (b[j],-d[j]) 在平面直角坐标系中表示出来：

寻找最优决策点的过程就可以看作平移一条斜率不变的直线，自下往上遇到的第一个点必然使截距最小，如图：

事实上，这个点就是和前面点斜率小于等于当前斜率，和后面点斜率大于等于当前斜率的点。

现在我们考虑改变直线斜率，发现可能是最优解的决策点当且仅当在下面的下凸包上：

不在下面的下凸包上的，无论斜率如何改变，都不可能是从下往上平移最小的点。

同理，对于 \min 的情况，会形成一个上凸包。

个人更喜欢几何法，比较直观，所以下面的例题都会采用几何法论证。

代码实现

对于不同的情况，我们有不同的插入决策点及查询最优解的方式（具体的可以看下面的例题）：

决策点横坐标（b[j]）严格增，直线方程斜率（a[i]）严格增

• 插入：可以维护一个队列存储决策点编号 j，由于决策点横坐标（b[j]）严格增，再根据凸包斜率严格增（或减）的性质，在插入时只要队列倒数第二元素和队尾的斜率小于（或大于）队尾和要插入的点的斜率，就弹出队尾，直到保证斜率严格增（或减）。
• 查询：根据最优决策点和前面点斜率小于（或大于）等于当前斜率，和后面点斜率大于（或小于）等于当前斜率的点，再根据直线方程斜率（a[i]）严格增，所以最优决策点横坐标严格增，不用保存前面的决策点，因此只要队首的两个元素斜率小于（或大于）当前斜率，就弹出队首，直到不能弹为止，队首就是最优决策点。
• 复杂度：O(n)。

决策点横坐标（b[j]）严格增，直线方程斜率（a[i]）不严格增

• 插入：由于决策点横坐标（b[j]）严格增不变，同上。
• 查询：由于直线方程斜率（a[i]）不严格增，所以最优决策点没有单调性了，此时只能根据凸包斜率的单调性二分找到和前面点斜率小于（或大于）等于当前斜率，和后面点斜率大于（或小于）等于当前斜率的点的点。
• 复杂度：O(n\log n)。

决策点横坐标（b[j]）不严格增

由于横坐标都不严格增，也就是说可能加的点在两点之间，上面的方法就行不通了。

可以考虑利用动态维护凸包或者采用 CDQ 分治离线等方法，在此先不予陈述。

这里介绍一种思维含量低、代码量小、常数小的优秀算法：李超线段树。

关于李超线段树本身的讲解可以看：浅谈李超线段树

事实上，李超线段树并不是维护动态凸包，而是利用本身的特性直接维护答案。

将一些不变量提出：

我们将 \min/\max 中的式子看作一个直线方程 y=kx+b，其中 b[j] 是斜率，a[i] 是此时横坐标，d[j] 是截距。

发现此时就是要求若干个直线 y=b[j]\cdot x+d[j] 在 x=a[i] 时的最值，而这恰好是李超线段树所维护的东西。

因此，每次我们只需将直线 y=b[j]\cdot x+d[j] 插入李超树，再查询所有直线在 x=a[i] 时的最值更新答案即可。

时间复杂度：O(n\log n)。

例题

P5785 [SDOI2012] 任务安排 link

题目描述

机器上有 n 个需要处理的任务，它们构成了一个序列。这些任务被标号为 1 到 n，因此序列的排列为 1 , 2 , 3 \cdots n。这 n 个任务被分成若干批，每批包含相邻的若干任务。从时刻 0 开始，这些任务被分批加工，第 i 个任务单独完成所需的时间是 T_i。在每批任务开始前，机器需要启动时间 s，而完成这批任务所需的时间是各个任务需要时间的总和。

注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 C_i。

请确定一个分组方案，使得总费用最小。

数据范围

解题思路

朴素 DP，不需要优化。

我们对 c 和 t 做前缀和，用前缀和替代原来的数组。

• 状态表示：dp[i] 表示完成前 i 个任务的最小费用。
• 初始化：dp[0]=0。
• 状态转移：考虑分配成的最后一组，设最后一组为 j+1\sim i，首先要在 dp[j] 的基础上加上 t[i] \cdot (c[i] - c[j])，但是 s 貌似比较难处理，发现 s 会对后面所有的任务产生影响，因此为方便处理，我们可以提前把它对后面的总贡献 s \cdot (c[n] - c[j]) 直接算进当前区间，因此有状态转移方程： dp[i] = \min(dp[j] + t[i] \cdot (c[i] - c[j]) + s \cdot (c[n] - c[j]))
• 答案：dp[n]。

时间复杂度：O(n^2)。

因为 1\leq n \leq 300000，O(n^2) 无法通过，发现状态转移方程符合斜率优化的条件，考虑斜率优化。

化简、移项得：

要使 dp[i] 更小，那么就要使截距尽可能小，因此决策点会形成一个下凸包。

由于 T_i,C_i \geq 1，因此前缀和严格增，所以横坐标 c[j] 严格增，截距 t[i]+s 严格增，应用第一种情况即可。

此时 -512\leq T_i \leq 512，所以截距不严格增，其他不变，在查询时二分找决策点即可。

编码技巧：在处理斜率时为避免误差，可以写作乘积的形式。

代码

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 5010;

int n, s;
ll t[N], f[N];
ll dp[N];

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i] >> f[i];
        t[i] = t[i - 1] + t[i];
        f[i] = f[i - 1] + f[i];
    }
    memset(dp, 0x7f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            dp[i] = min(dp[i], dp[j] + t[i] * (f[i] - f[j]) + s * (f[n] - f[j]));
        }
    }
    cout << dp[n] << endl;
    return 0;
}

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 3e5 + 10;

int n, s;
int t[N], c[N];
int dp[N], q[N];

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }
    int hh = 0, tt = 0;
    q[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        while (hh < tt && (dp[q[hh + 1]] - dp[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]]))
        {
            hh++;
        }
        dp[i] = dp[q[hh]] + t[i] * (c[i] - c[q[hh]]) + s * (c[n] - c[q[hh]]);
        while (hh < tt && (dp[q[tt]] - dp[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (dp[i] - dp[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))
        {
            tt--;
        }
        q[++tt] = i;
    }
    cout << dp[n] << endl;
    return 0;
}

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 3e5 + 10;

int n, s;
ll t[N], c[N];
ll dp[N], q[N];

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }
    int hh = 0, tt = 0;
    q[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = hh, r = tt;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (dp[q[mid + 1]] - dp[q[mid]] > (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        dp[i] = dp[q[r]] + t[i] * (c[i] - c[q[r]]) + s * (c[n] - c[q[r]]);
        while (hh < tt && (dp[q[tt]] - dp[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (dp[i] - dp[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))
        {
            tt--;
        }
        q[++tt] = i;
    }
    cout << dp[n] << endl;
    return 0;
}

P4655 [CEOI 2017] Building Bridges link

题目描述

有 n 根柱子依次排列，每根柱子都有一个高度。第 i 根柱子的高度为 h_i。

现在想要建造若干座桥，如果一座桥架在第 i 根柱子和第 j 根柱子之间，那么需要 (h_i-h_j)^2​​ 的代价。

在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 i 根柱子被拆除的代价为 w_i，注意 w_i 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 1 根柱子和第 n 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

数据范围

• 状态转移：考虑柱子 i 和 j 相接，则有： dp[i]=\min(dp[j]+(h[i]-h[j])^2+w[i-1]-w[j])
• 答案：dp[n]。

现在考虑斜率优化，移项：

发现由于原来的 h[i] 可以为 0，因此横坐标 h[j] 不严格增，只能用李超线段树优化。

将式子化为：

问题转化为：每次插入直线 y=-2h[j]\cdot x+dp[j]+h[j]^2-w[j]，求在 x=h[i] 时的最小值。

用李超线段树维护即可，时间复杂度 O(n\log n)。

代码

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n;
long long h[N], w[N];
long long dp[N];

struct line
{
    long long k, b;

    inline long long calc(long long x)
    {
        return k * (x - 1) + b;
    }
} p[N];

struct SGT
{
    #define ls x << 1
    #define rs x << 1 | 1
    #define mid ((l + r) >> 1)
    int dat[M << 2];

    void update(int x, int l, int r, int k)
    {
        if (!dat[x])
        {
            dat[x] = k;
            return;
        }
        if (p[k].calc(mid) < p[dat[x]].calc(mid))
        {
            swap(k, dat[x]);
        }
        if (p[k].calc(l) < p[dat[x]].calc(l))
        {
            update(ls, l, mid, k);
        }
        if (p[k].calc(r) < p[dat[x]].calc(r))
        {
            update(rs, mid + 1, r, k);
        }
    }

    long long query(int x, int l, int r, int k)
    {
        if (r < k || l > k)
        {
            return 1e18;
        }
        long long res = p[dat[x]].calc(k);
        if (l == r)
        {
            return res;
        }
        return min(res, min(query(ls, l, mid, k), query(rs, mid + 1, r, k)));
    }
} t;

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    p[0].b = 1e18;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        w[i] = w[i] + w[i - 1];
    }
    p[1].k = -2 * h[1], p[1].b = h[1] * h[1] - w[1];
    t.update(1, 1, M, 1);
    for (int i = 2; i <= n; i++)
    {
        dp[i] = h[i] * h[i] + w[i - 1] + t.query(1, 1, M, h[i] + 1);
        p[i].k = -2 * h[i], p[i].b = dp[i] + h[i] * h[i] - w[i];
        t.update(1, 1, M, i);
    }
    cout << dp[n] << endl;
    return 0;
}

P4072 [SDOI2016] 征途 link

题目描述

Pine 开始了从 S 地到 T 地的征途。

从 S 地到 T 地的路可以划分成 n 段，相邻两段路的分界点设有休息站。

Pine 计划用 m 天到达 T 地。除第 m 天外，每一天晚上 Pine 都必须在休息站过夜。所以，一段路必须在同一天中走完。

Pine 希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。

帮助 Pine 求出最小方差是多少。

设方差是 v，可以证明，v\times m^2 是一个整数。为了避免精度误差，输出结果时输出 v\times m^2。

数据范围

• 对于所有 j (1 \leq j < k)，满足 y_{sj} = x_{s_{j+1}} 且 q_{sj}\leq p_{s_{j+1}}

对于该回家路线，小猫得到的烦躁值将为：

小猫想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。

数据范围

对于所有的测试点，保证 2\le n\le 10^5，1\le m\le 10^6，0\le A\le 10，0\le B,C\le 10^7，1\le x_i,y_i\le n，x_i\neq y_i，0\le p_i<q_i\le 4\times 10^4。

解题思路

考虑 DP。

首先我们可以先不考虑到达 n 号站点增加的烦躁值，最后把它算上即可，因此下文指的最小烦躁值都不包含这一项。

• 状态表示：这道题要在状态表示上做点文章，如果用 dp[i] 表示到达 i 站点的最小烦躁值，发现难以转移，而再加一维时间，时间和空间复杂度都难以接受，因此我们可以用 dp[i] 表示乘坐 i 号列车到达 y_i 号站点的最小烦躁值，用一维就可以包含时间和空间。
• 初始化：dp[0]=0。
• 状态转移：考虑从 j 列车换乘到 i 列车，则有： dp[i]=\min_{x_i=y_j,p_i>q_j}(dp[j]+A(p_i-q_j)^2+B(p_i-q_j)+C)
• 答案：\min_{y_i=n}(dp[i]+q_i)。

时间复杂度 O(m^2)，考虑斜率优化：

我们先考虑两个限制如何处理：

• 对于 x_i=y_j，我们只需开 n 个单调队列，查询从 x_i 号单调队列中取，插入到第 y_i 号单调队列即可。
• 对于 p_i>q_j，我们可以考虑在查询时让单调队列中所有 q_j 都小于等于 p_i，具体地，由于 0\le p_i,q_i\le 4\times 10^4，因此我们可以用桶存储代替堆，插入时先不插进单调队列，把它放进键值为 q_i 的桶中，然后在查询的时候统一把键值小于 p_i 的桶中的元素都插入单调队列。

发现对于第二个限制的处理方法，要求 p_i 不降，于是我们一开始便可以将 p_i 排序。

由于我们插入是按桶的顺序插入的，所以 q_j 也顺带着不降了，因此斜率和横坐标都不降。

要使 dp[i] 更小，就要使截距更小，因此最优决策点构成一个下凸包，应用第一种情况即可。

时间复杂度 O(m\log m)。

代码

#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

struct node
{
    ll x, y, p, q;
} tr[M];

ll n, m, a, b, c, lst = 0, ans = LONG_LONG_MAX;
ll dp[M];
vector<int> e[N];

struct que
{
    int h = 0, t = -1;
    vector<ll> q;

    inline ll X(int x)
    {
        return tr[x].q;
    }

    inline ll Y(int x)
    {
        return dp[x] + a * tr[x].q * tr[x].q - b * tr[x].q;
    }

    ll query(int x)
    {
        if (h > t)
        {
            return -1;
        }
        while (h < t && (Y(q[h + 1]) - Y(q[h])) <= 2 * a * tr[x].p * (X(q[h + 1]) - X(q[h])))
        {
            h++;
        }
        return q[h];
    }

    void insert(int x)
    {
        while (h < t && (Y(q[t]) - Y(q[t - 1])) * (X(x) - X(q[t])) >= (Y(x) - Y(q[t])) * (X(q[t]) - X(q[t - 1])))
        {
            q.pop_back();
            t--;
        }
        q.push_back(x);
        t++;
    }
} q[N];

bool cmp(node x, node y)
{
    return x.p < y.p;
}

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> a >> b >> c;
    for (int i = 1; i <= m; i++)
    {
        cin >> tr[i].x >> tr[i].y >> tr[i].p >> tr[i].q;
    }
    sort(tr + 1, tr + m + 1, cmp);
    q[1].insert(0);
    for (int i = 1; i <= m; i++)
    {
        for (; lst <= tr[i].p; lst++)
        {
            for (auto it : e[lst])
            {
                q[tr[it].y].insert(it);
            }
        }
        int j = q[tr[i].x].query(i);
        if (j == -1)
        {
            continue;
        }
        dp[i] = dp[j] + a * (tr[i].p - tr[j].q) * (tr[i].p - tr[j].q) + b * (tr[i].p - tr[j].q) + c;
        e[tr[i].q].push_back(i);
        if (tr[i].y == n)
        {
            ans = min(dp[i] + tr[i].q, ans);
        }
    }
    cout << ans << endl;
    return 0;
}

结语

看了这么多，恭喜你学会了斜率优化！！！

有没有人和你说过，你学 OI 的样子真的很帅。

如果没有？

那么，就在上一秒，我对你说了。