抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

学习笔记《斜率优化》

学习笔记

发布于：2025年7月27日

简述

对于一个 dpi=min⁡/max⁡j=1i+val(i,j)dp_i = {\min/\max}_{j=1}^i + val(i, j)。
如果 valval 中同时有和 i,ji, j 相关的项，我们就不能直接用单调队列优化。
如果 val(i,j)=ci+dj+eifjval(i, j) = c_i + d_j + e_if_j 的形式，我们可以使用斜率优化。

我们考虑 jj 比 j′j' 更优的情况（这里用 min⁡\min 举例）。

dpj+dj+eifj<dpj′+dj′+eifj′ei(fj−fj′)<(dpj′+dj′)−(dpj+dj)ei<(dpj′+dj′)−(dpj+dj)fj−fj′\begin{aligned} &dp_j + d_j + e_if_j < dp_{j'} + d_{j'} + e_if_{j'}\\ &e_i(f_j - f_{j'}) < (dp_{j'} + d_{j'}) - (dp_j + d_j)\\ &e_i < \dfrac{(dp_{j'} + d_{j'}) - (dp_j + d_j)}{f_j - f_{j'}} \end{aligned}

右边的很像斜率，我们令 PiP_i 为二维平面上的 (fj,dpi+di)(f_j, dp_i + d_i)。
即 dpj+djdp_j + d_j 看成纵坐标，fjf_j 作为横坐标，现在我们比较两个点的斜率即可。
有个显然的结论，可能成为最优点的会形成凸壳。
在大部分时候，取 min 用下凸壳，取 max 用上凸壳。

Ex.1

P2365 任务安排
O(n3)O(n^3) 的 DP 是显然的 dpi,k=min⁡j=1n−1dpj,k−1+(∑w=j+1itw+sk)(∑w=j+1ifw)dp_{i, k} = \min_{j=1}^{n-1} dp_{j,k-1}+(\sum_{w=j+1}^i t_w+sk)(\sum_{w=j+1}^i f_w)，考虑优化。
如果多分一段，那么后面的所有数都要加 sfsf，所以我们可以提前加在 dpidp_i，并对 t,ft, f 做前缀和。
即 dpi=min⁡j=1n−1dpj+(fi−fj)ti+s(fn−fj)dp_i = \min_{j=1}^{n-1} dp_j + (f_i-f_j)t_i + s(f_n-f_j)。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}

P10979 任务安排2
考虑 n≤3×105n \le 3\times 10^5 怎么做，我们可以斜率优化。
我们拆一下式子（为方便不写 min⁡\min）：
dpi=dpj+sfn+fiti−(s+ti)fjdp_i = dp_j + sf_n + f_it_i - (s + t_i)f_j
这里用 dpjdp_j 为纵坐标，fjf_j 为横坐标，s+tis+t_i 为斜率。
这里要维护下凸壳，由于 tit_i 是单调上升的，所以斜率也上升，当 fif_i 也单调上升。
在斜率和横坐标单调上升时，那么求答案时可以直接淘汰比斜率小的，且每次加点在最右边，可以用单调队列做到 O(n)O(n)。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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
此题的 tit_i 可能是负数，斜率不再单调，就不能直接淘汰小于的部分了。
由于下凸壳的斜率递增，我们可以用单调栈，询问时二分，复杂度 O(nlog⁡n)O(n \log n)。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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);
        // cout << p << " ";
        f[i] = f[p] - k * b[p] + a[i] * b[i] + s * b[n];
        // cout << f[i] << endl;
        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
我们先考虑 O(n2)O(n^2) 的 dpi=min⁡j=0i−1dpj+(hi−hj)2−(swi−1−swj)dp_i = \min_{j=0}^{i-1}dp_j+(h_i-h_j)^2-(sw_{i-1}-sw_j)。
然后愉快的拆式子。

dpi=dpj+hi2+hj2−2hihj−swi−1+swjdpi=(dpj+swj+hj2)−2hihj+(hi2−swi−1)\begin{aligned} &dp_i = dp_j+h_i^2+h_j^2-2h_ih_j-sw_{i-1}+sw_j\\ &dp_i = (dp_j+sw_j+h_j^2)-2h_ih_j+(h_i^2-sw_{i-1}) \end{aligned}

我们以 dpj−swj+hj2dp_j-sw_j+h_j^2 为纵坐标，hjh_j 为横坐标，−2hi-2h_i 为斜率。
但是我们没有对 hh 做前缀和，hh 并不是单调的，每次加点并不一定在最右边。
一种方法是用平衡树动态维护凸壳（我不会）。
第二种是用 cdq，由于右边不会影响左边的 ff，先递归左边，然后排序左侧建凸壳，更新 [mid+1,r][mid+1,r] 的答案，最后递归右边。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}

第三种是用李超线段树，每次插入 y=(−2hj)x+(dpj−swj+hj2)y=(-2h_j)x+(dp_j-sw_j+h_j^2) 的直线，询问 x=hix=h_i 时的最小值。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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 征途

vm2=∑i=1m(Sm−vi)2m×m2=(∑i=1mS2m2+vi2−2viSm)×m=S2+∑i=1mmvi2−2Svi=−S2+m∑i=1mvi2\begin{aligned} vm^2 &= \dfrac{\sum_{i = 1}^{m} \left(\frac{S}{m} - v_i\right)^2}{m}\times m^2 \\ &= \left(\sum_{i = 1}^{m} \frac{S^2}{m^2}+v_i^2-2v_i\frac{S}{m}\right)\times m\\ &= S^2 + \sum_{i=1}^{m} mv_i^2 - 2Sv_i\\ &= -S^2 + m\sum_{i=1}^{m} v_i^2 \end{aligned}

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

fi,k=min⁡j=k−1i−1fj,k−1+(si−sj)2\begin{aligned} f_{i, k} &= \min_{j = k-1}^{i - 1}{f_{j, k-1} + (s_i - s_j)^2}\\ \end{aligned}

此时答案是 mfn,m−sn2mf_{n, m}-s_n^2，由于 n≤3000n \le 3000。
我们先枚举 kk，则上面的式子可以斜率优化。
fi,k=(fj,k−1+sj2)+si2−2sisjf_{i, k} = (f_{j, k-1}+s_j^2) + s_i^2 - 2s_is_j
我们以 fj,k−1+sj2f_{j, k-1} + s_j^2 为纵坐标，以 sjs_j 为横坐标，斜率为 2si2s_i。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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
k≤20k \le 20，我们枚举 kk 轮。
用上轮的答案计算再用 11 次航班后，每个点的最小值。
然后每次做最短路即可。

中间计算用斜率优化 DP 即可，ff 是这轮的最小值，gg 是上轮的。

fi=gj+(i−j)2=(gj+j2)−2ij+i2\begin{aligned} f_i &= g_j + (i - j) ^ 2\\ &= (g_j+j^2) - 2ij + i^2 \end{aligned}

这里 gj+j2g_j+j^2 为纵坐标，jj 为横坐标，−2i-2i 为斜率。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
struct A{int x, dis;bool operator<(const A&j)const{return dis > j.dis;}};
priority_queue<A>p;
int f[N], n, m, k, q[N], g[N];
vt<PII>e[N];
void dij(){
    while(!p.empty()){
        int x = p.top().x, w = p.top().dis;
        if(p.pop(), w != f[x])continue;
        for(PII v : e[x])if(f[v.fr] > (w = f[x] + v.se))
            f[v.fr] = w, p.push({v.fr, w});
    }
}
int X(int x){return x;}
int Y(int x){return g[x] + x * x;}
double slope(int x, int y){
    return (double)(Y(y) - Y(x)) / (X(y) - X(x));
}
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int u, v, w, l, r;
    cin >> n >> m >> k;
    FL(i, 1, m)cin >> u >> v >> w, e[u].eb(v, w), e[v].eb(u, w);
    memset(f, 0x3f, sizeof f), f[1] = 0, p.push({1, 0}), dij();
    while(k--){
        q[l = r = 1] = 0;
        FL(i, 1, n)g[i] = f[i];
        FL(i, 1, n){
            while(l < r && slope(q[r - 1], q[r]) > slope(q[r], i))r--;
            q[++r] = i;
        }
        FL(i, 1, n){
            while(l < r && slope(q[l], q[l + 1]) < 2 * i)l++;
            int k = q[l];
            if(f[i] > (k = g[k] + (i - k) * (i - k)))
                f[i] = k, p.push({i, k});
        }
        dij();
    }
    FL(i, 1, n)cout << f[i] << " ";
    return 0;
}

更新于：2025年7月27日

DP

斜率优化