学习笔记《斜率优化》

fush · 2025-10-28 14:18:28 · 算法·理论

简述

对于一个 dp_i = {\min/\max}_{j=1}^i dp_j + C_i + C_j + F_iF_j。
由于转移中有同时和 i, j 相关的项，所以不能用单调队列优化。
所以需要斜率优化。

维护凸包

接下来以 \min 举例。
我们把式子改写为 dp_j+C_j=-F_iF_j+(dp_i-C_i)。
设 y=dp_j+C_j, x=F_j, k=-F_i, b=dp_i-C_i。
现在我们希望 b 越小越好，考虑怎么做。
我们把每个决策点变成平面上的点 (x, y)。
那么一条斜率为 k 的直线从下往上第一个碰到的点就是最优决策点。
我们考虑 j 比 j' 更优的情况。

显然可能最优决策点的点会形成凸壳，考虑如何维护。
在大部分时候，取 \min 用下凸壳，取 \max 用上凸壳。

如果每次加入的点在最右边，用单调队列维护。
那么由于在最右边，所以肯定在凸壳内，然后向前删除不优的点即可。
如果 k 单调不降，每次从左往右，不优的点直接扔掉就好了。
否则就只能二分了。

如果不在最右边，可以用平衡树维护凸壳。
或者用 CDQ 离线处理。
由于右边不会成为左边决策点，所以先求左边，然后排序左侧建凸壳，更新 [mid+1,r] 的答案后，继续递归右边。

维护直线

我们把 dp_i=dp_j+C_i+C_j+F_jF_j 改写成 dp_i-C_i=F_jF_i+(dp_j+F_j)。
然后把决策点 j 看成 y=F_jx+(dp_j+F_j) 的一次函数。
每次要知道 x=F_i 时的最小值就好了，可以用李超线段树直接维护。

P2365 任务安排

设 x=dp_j,y=f_j,k=s+t_i。

::::info[代码]

#include<bits/stdc++.h>   
using namespace std;   
#define endl '\n'   
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)   
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)   
#define lowbit(x) ((x)&-(x))   
#define eb emplace_back   
#define SZ(x) (int)((x).size())   
#define int long long   
#define vt vector   
#define fr first   
#define se second   
#define ar(x) array<int,x>   
#define PII pair<int, int>   
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})   
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})   
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})   
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})   
constexpr int N = 1e6 + 10;   
int n, s, a[N], b[N], f[N], q[N];   
int32_t main(){   
    cin.tie(0)->sync_with_stdio(0);   
    cin >> n >> s;   
    FL(i, 1, n)cin >> a[i] >> b[i], a[i] += a[i - 1], b[i] += b[i - 1];   
    int l = 1, r = 1;   
    FL(i, 1, n){   
        int k = s + a[i];   
        while(l < r && f[q[l + 1]] - f[q[l]] <= k * (b[q[l + 1]] - b[q[l]]))l++;//直接淘汰   
        f[i] = f[q[l]] - k * b[q[l]] + a[i] * b[i] + s * b[n];   
        while(l < r && (f[q[r]] - f[q[r - 1]]) * (b[i] - b[q[r]]) >= (b[q[r]] - b[q[r - 1]]) * (f[i] - f[q[r]]))--r;//维护下凸壳   
        q[++r] = i;   
    }   
    cout << f[n];   
    return 0;   
}   

::::

P5785 任务安排3
此题的 t_i 可能是负数，斜率不再单调，就不能直接淘汰小于的部分了。
由于下凸壳的斜率递增，我们可以用单调栈，询问时二分，复杂度 O(n \log n)。

::::info[代码]

#include<bits/stdc++.h>   
using namespace std;   
#define endl '\n'   
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)   
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)   
#define lowbit(x) ((x)&-(x))   
#define eb emplace_back   
#define SZ(x) (int)((x).size())   
#define int long long   
#define vt vector   
#define fr first   
#define se second   
#define ar(x) array<int,x>   
#define PII pair<int, int>   
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})   
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})   
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})   
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})   
constexpr int N = 1e6 + 10;   
int n, s, a[N], b[N], f[N], q[N];   
int find(int k, int l, int r){   
    if(l == r)return q[l];   
    while(l < r){   
        int m = l + r + 1 >> 1;   
        if(f[q[m]] - f[q[m - 1]] <= k * (b[q[m]] - b[q[m - 1]]))l = m;   
        else r = m - 1;   
    }   
    return q[l];   
}   
int32_t main(){   
    cin.tie(0)->sync_with_stdio(0);   
    cin >> n >> s;   
    FL(i, 1, n)cin >> a[i] >> b[i], a[i] += a[i - 1], b[i] += b[i - 1];   
    int l = 1, r = 1;   
    FL(i, 1, n){   
        int k = s + a[i], p = find(k, l, r);   
        f[i] = f[p] - k * b[p] + a[i] * b[i] + s * b[n];   
        while(l < r && (f[q[r]] - f[q[r - 1]]) * (b[i] - b[q[r]]) >= (b[q[r]] - b[q[r - 1]]) * (f[i] - f[q[r]]))--r;   
        q[++r] = i;   
    }   
    cout << f[n];   
    return 0;   
}   

::::

Ex.2

P4655 Building Bridges
我们设 sw_i = \sum_{j=1}^i w_j。
然后考虑 O(n^2) 的 dp_i = \min_{j=0}^{i-1}dp_j+(h_i-h_j)^2+(sw_{i-1}-sw_j)。
然后愉快的拆式子。

设 x=h_j,y=dp_j-sw_j+h_j^2,k=-2h_i。
但是我们没有对 h 做前缀和，h 并不是单调的，所以每次加点并不一定在最右边。

::::info[CDQ]

#include<bits/stdc++.h>   
using namespace std;   
#define endl '\n'   
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)   
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)   
#define lowbit(x) ((x)&-(x))   
#define eb emplace_back   
#define SZ(x) (int)((x).size())   
#define int long long   
#define vt vector   
#define fr first   
#define se second   
#define ar(x) array<int,x>   
#define PII pair<int, int>   
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})   
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})   
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})   
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})   
constexpr int N = 1e6 + 10;   
int n, h[N], w[N], s[N], Y[N], X[N], dp[N], pos[N], q[N];   
long double slope(int j, int k){   
    if (X[k] == X[j])return Y[k] > Y[j] ? 1e20 : -1e20;   
    return (long double)(Y[k] - Y[j]) / (X[k] - X[j]);   
}   
void solve(int l, int r){   
    if (l == r)   
        return l = pos[l], Y[l] = dp[l] - s[l] + h[l] * h[l], X[l] = h[l], void();   
    int mid = (l + r) >> 1;   
    stable_partition(pos + l, pos + r + 1, [&](int&x){return x <= mid;});   
    solve(l, mid);   
    int L = 1, R = 0;   
    FL(i, l, mid){   
        while(L < R && slope(q[R], pos[i]) <= slope(q[R - 1], q[R]))R--;   
        q[++R] = pos[i];   
    }   
    FL(i, mid + 1, r){   
        int k = pos[i];   
        while(L < R && slope(q[L], q[L + 1]) <= 2 * h[k])L++;   
        cmin(dp[k], dp[q[L]] + (h[k] - h[q[L]]) * (h[k] - h[q[L]]) + s[k - 1] - s[q[L]]);   
    }   
    solve(mid + 1, r);   
    inplace_merge(pos+l, pos+mid+1, pos+r+1, [&](int x, int y){return h[x] < h[y];});   
}   
int32_t main(){   
    cin.tie(0)->sync_with_stdio(0);   
    cin >> n;   
    FL(i, 1, n)cin >> h[i], pos[i] = i;   
    FL(i, 1, n)cin >> w[i], s[i] = s[i - 1] + w[i];   
    sort(pos + 1, pos + 1 + n, [&](int&x, int&y){return h[x] < h[y];});   
    memset(dp, 0x7f, sizeof dp), dp[1] = 0, solve(1, n), cout << dp[n];   
    return 0;   
}   

::::

::::info[李超线段树]

#include<bits/stdc++.h>   
using namespace std;   
#define endl '\n'   
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)   
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)   
#define lowbit(x) ((x)&-(x))   
#define eb emplace_back   
#define SZ(x) (int)((x).size())   
#define int long long   
#define vt vector   
#define fr first   
#define se second   
#define ar(x) array<int,x>   
#define PII pair<int, int>   
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})   
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})   
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})   
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})   
constexpr int N = 1e6 + 10;   
int h[N], w[N], dp[N], s[N], sg[N << 1], n;   
struct A{int a, b;int g(int x){return b + a * x;}}line[N];   
void modify(int u, int l, int r, int t){   
    if(!sg[u])return void(sg[u] = t);   
    if(l == r)return (line[sg[u]].g(l) > line[t].g(l)) && (sg[u] = t), void();   
    int mid = l + r >> 1;   
    if(line[t].g(mid) < line[sg[u]].g(mid))swap(t, sg[u]);   
    if(line[t].g(l) < line[sg[u]].g(l))modify(u << 1, l, mid, t);   
    if(line[t].g(r) < line[sg[u]].g(r))modify(u << 1 | 1, mid + 1, r, t);   
}   
int query(int u, int l, int r, int v){   
    if(l == r)return line[sg[u]].g(v);   
    int mid = l + r >> 1, ans = line[sg[u]].g(v);   
    if(v <= mid)return min(ans, query(u << 1, l, mid, v));   
    return min(ans, query(u << 1 | 1, mid + 1, r, v));   
}   
int32_t main(){   
    cin.tie(0)->sync_with_stdio(0);   
    cin >> n, line[0].b = 1e18;   
    FL(i, 1, n)cin >> h[i];   
    FL(i, 1, n)cin >> w[i], s[i] = s[i - 1] + w[i];   
    line[1] = {-2 * h[1], h[1] * h[1] - w[1]}, modify(1, 0, 1e6, 1);   
    FL(i, 2, n){   
        dp[i] = h[i] * h[i] + s[i - 1] + query(1, 0, 1e6, h[i]);   
        line[i] = {-2 * h[i], dp[i] + h[i] * h[i] - s[i]}, modify(1, 0, 1e6, i);   
    }   
    cout << dp[n];   
    return 0;   
}   

::::

Ex.3

P4072 征途

我们带入 dp，设 f_{i, k} 表示前 i 分成 k 段时的最小值。

此时答案是 mf_{n, m}-s_n^2，由于 n \le 3000。
我们先枚举 k，则上面的式子可以斜率优化。

设 x=s_j,y=f_{j, k-1} + s_j^2,k=2s_i。

::::info[代码]

#include<bits/stdc++.h>   
using namespace std;   
#define endl '\n'   
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)   
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)   
#define lowbit(x) ((x)&-(x))   
#define eb emplace_back   
#define SZ(x) (int)((x).size())   
#define int long long   
#define vt vector   
#define fr first   
#define se second   
#define ar(x) array<int,x>   
#define PII pair<int, int>   
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})   
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})   
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})   
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})   
constexpr int N = 1e6 + 10;   
int s[N], f[N], g[N], q[N];   
int X(int x){return s[x];}   
int Y(int x){return s[x] * s[x] + g[x];}   
int32_t main(){   
    cin.tie(0)->sync_with_stdio(0);   
    int n, m;   
    cin >> n >> m;   
    FL(i, 1, n)cin >> s[i], s[i] += s[i - 1];   
    FL(i, 1, n) g[i] = s[i] * s[i];   
    FL(k, 2, m){   
        int l = 1, r = 1;   
        q[l] = k - 1;   
        FL(i, k, n){   
            while(l < r && Y(q[l + 1]) - Y(q[l]) < (X(q[l + 1]) - X(q[l])) * 2 * s[i])++l;   
            f[i] = g[q[l]] + (s[i] - s[q[l]]) * (s[i] - s[q[l]]);   
            while(l < r && (Y(q[r]) - Y(q[r - 1])) * (X(i) - X(q[r])) > (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r - 1])))r--;   
            q[++r] = i;   
        }   
        FL(i, 1, n)g[i] = f[i];   
    }   
    // cout << s[n] << " " << f[n] << endl;   
    cout << f[n] * m - s[n] * s[n];   
    return 0;   
}   

::::

Ex.4

CF1715E Long Way Home