BHX
斜率优化DP

斜率优化DP

2025年04月15日 2.4k 字 大概 13 分钟

前言

斜率优化DP一般是形如 \(f_{i}=\min _{j=0}^{i-1}\left\{c_j+x_{i} k_{j}\right\}+w_i\)的DP方程。
显然，我们可以使用李超线段树维护 \(y=k_i \cdot x +f_i\)的线段，然后求 \(dp_i\) 时在第 \(x=x_i\) 求解。时间复杂度一般为 \(O(n\log n)\)。

P4655 [CEOI 2017] Building Bridges

题目链接

将 \(w\) 进行前缀和，有一个显然的 \(dp\) 式子，即 \(f_i=\min_{j=1}^{i-1}\{f_j+h_i^2+h_j^2-2h_ih_j+w_{i-1}-w_j\}\)。

我们将式子进行化简即可得到 \(f_i=\min_{j=1}^{i-1}\{-2h_ih_j+f_j+h_j^2-w_j\}+h_i^2+w_{i-1}\)，可以看出这是标准的斜率优化式子，我们令 \(-2h_j\) 为 \(k\) ，\(h_j^2-w_j\) 为 \(b\) ，把 \(h_i\) 当作 \(x\) ，向李超线段树中加入这些线段即可，时间复杂度 \(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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define db double
#define rg register
#define pb push_back
#define pob pop_back
#define pii pair<int,int>
#define vi vector<int>
#define fr first
#define sc second
#define endl '\n'
#define int long long
using namespace std;
const int inf=2e18;
const int maxn=1e6+10;

int tr[maxn*4],h[maxn],w[maxn],dp[maxn],k[maxn],b[maxn];
int n;

int read() {
    int f=1,x=0;
    char c;
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }while(isdigit(c)) {
        x=(x<<1)+(x<<3)+(c-'0');
        c=getchar();
    }return x*f;
}

int calc(int x,int id) {
    return k[id]*x+b[id];
}

void update(int id,int l,int r,int val) {
    if(l==r) {
        if(calc(l,val)<calc(l,tr[id])) tr[id]=val;
        return;
    } int mid=(l+r)/2;
    if(calc(mid,val)<calc(mid,tr[id])) swap(val,tr[id]);
    if(calc(l,val)<calc(l,tr[id])) update(id*2,l,mid,val);
    else if(calc(r,val)<calc(r,tr[id])) update(id*2+1,mid+1,r,val);
}

int query(int id,int l,int r,int pos) {
    if(l==r) return calc(pos,tr[id]);
    int mid=(l+r)/2;
    if(pos<=mid) return min(calc(pos,tr[id]),query(id*2,l,mid,pos));
    else return min(calc(pos,tr[id]),query(id*2+1,mid+1,r,pos));
}

signed main() {
    n=read(); b[0]=inf;
    for(int i=1;i<=n;i++) h[i]=read();
    for(int i=1;i<=n;i++) {
        w[i]=read(); w[i]+=w[i-1];
    }
    k[1]=-2*h[1],b[1]=h[1]*h[1]-w[1];
    update(1,0,maxn-1,1);
    for(int i=2;i<=n;i++) {
        dp[i]=h[i]*h[i]+w[i-1]+query(1,0,maxn-1,h[i]);
        k[i]=-2*h[i],b[i]=dp[i]+h[i]*h[i]-w[i],update(1,0,maxn-1,i);
    }
    cout<<dp[n]<<'\n';
    return 0;
}

P3628 [APIO2010] 特别行动队

题目链接

令 \(s\) 为 \(x\) 的前缀和数组，这里直接给出推广后的式子，即 \(dp_i=\max_{j=0}^{i-1}\{-2as_is_j+dp_j+as_j^2-bs_j\}+as_i^2+bs_i+c\)。

注意此题 \(j\) 从 \(0\) 开始与上题不同，并且注意这里的 \(x\) 为 \(s\) 数组，值域达到了 \(1e8\)，所以要使用动态开点。

代码: 

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
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define db double
#define rg register
#define pb push_back
#define pob pop_back
#define pii pair<int,int>
#define vi vector<int>
#define fr first
#define sc second
#define endl '\n'
#define int long long
using namespace std;
const int inf=2e18;
const int maxn=2e6+10;
const int maxm=1e8+5;

int read() {
    int f=1,x=0;
    char c;
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }while(isdigit(c)) {
        x=(x<<1)+(x<<3)+(c-'0');
        c=getchar();
    }return x*f;
}

int lc[maxn],rc[maxn],tr[maxn],a,b,c;
int s[maxn],n,idx,rt;
int k[maxn],x[maxn];
int dp[maxn];
int get(int id,int val) {return x[id]+k[id]*val;}

void update(int &u,int l,int r,int val) {
    if(!u) u=++idx;
    if(l==r) {
        if(get(val,l)>get(tr[u],l)) tr[u]=val;
        return;
    }
    int mid=(l+r)/2;
    if(get(val,mid)>get(tr[u],mid)) swap(val,tr[u]);
    if(get(val,l)>get(tr[u],l)) update(lc[u],l,mid,val);
    else if(get(val,r)>get(tr[u],r)) update(rc[u],mid+1,r,val);
}

int query(int u,int l,int r,int pos) {
    if(!u) return -inf;
    if(l==r) return get(tr[u],pos);
    int mid=(l+r)/2;
    if(pos<=mid) return max(get(tr[u],pos),query(lc[u],l,mid,pos));
    else return max(get(tr[u],pos),query(rc[u],mid+1,r,pos));
}

signed main() {
    n=read(); a=read(),b=read(),c=read(); 
    memset(x,-0x3f,sizeof x);
    for(int i=1;i<=n;i++) {
        s[i]=read();
        s[i]+=s[i-1];
    }
    k[0]=0,x[0]=0; update(rt,0,maxm-1,0);
    for(int i=1;i<=n;i++) {
        dp[i]=s[i]*s[i]*a+s[i]*b+c+query(rt,0,maxm-1,s[i]);
        k[i]=-2*a*s[i],x[i]=dp[i]+s[i]*s[i]*a-s[i]*b; update(rt,0,maxm-1,i);
    } cout<<dp[n]<<'\n';
    return 0;
}

P8632 [蓝桥杯 2015 国 B] 居民集会

题目链接

记 \(f_{i, t}(0 \leq i \leq l, 0 \leq t \leq 4)\) 为在离起点距离为 \(i\) 处建第 \(t\) 个集合点的最小花费。特别地，我们认为 \(f_{0,0},f_{1,0},\cdots,f_{n, 0}=0\) ,答案即为 \(f_{L,4}\)。

\[ f_{i, t}=\min \left\{f_{j, t-1}+(i-j-1) \cdot s_{j+1}+(i-j-2) \cdot s_{j+2}+\cdots+(i-i) \cdot s_{i}\right\}(0 \le j \leq i) \]

变换式子,得：

\[ f_{i, t}=\min \left\{f_{i, t-1}+i \cdot\left(s_{j+1}+s_{j+2}+\cdots\right)-\left((j+1) \cdot s_{j+1}+(j+2) \cdot s_{j+2}+\cdots+i \cdot s_{i}\right)\right] \]

记 \(sum1_i=\sum_{j=0}^{i}s_j\), \(sum2_i=\sum_{j=0}^{i}s_i \cdot i\),可将继续变换为前缀和的形式：

\[ f_{i, t}=\min \left\{f_{j, t-1}+i \cdot\left(s u m 1_{i}-\operatorname{sum} 1_{j}\right)-\left(s u m 2_{i}-\operatorname{sum} 2_{j}\right)\right\} \]

去掉括号，写成斜优的标准形式如下：

\[ f_{i, t}=\min \left\{-\operatorname{sum} 1_{j} \cdot i+\operatorname{sum} 2_{j}+f_{j, t-1}\right\}+i \cdot \operatorname{sum} 1_{i}-\operatorname{sum} 2_{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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
#define db double
#define rg register
#define pb push_back
#define pob pop_back
#define pii pair<int,int>
#define vi vector<int>
#define fr first
#define sc second
#define endl '\n'
#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e6+10;

int s[maxn],sum1[maxn],sum2[maxn];
int n,l;
int k[maxn],b[maxn];
int tr[maxn*4];
int dp[maxn][5];
int read() {
    int f=1,x=0;
    char c;
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }while(isdigit(c)) {
        x=(x<<1)+(x<<3)+(c-'0');
        c=getchar();
    }return x*f;
}

int calc(int x,int id) {
    return k[id]*x+b[id];
}

void update(int id,int l,int r,int val) {
    if(l==r) {
        if(calc(l,val)<calc(l,tr[id])) tr[id]=val;
        return;
    } int mid=(l+r)/2;
    if(calc(mid,val)<calc(mid,tr[id])) swap(val,tr[id]);
    if(calc(l,val)<calc(l,tr[id])) update(id*2,l,mid,val);
    else if(calc(r,val)<calc(r,tr[id])) update(id*2+1,mid+1,r,val);
}

int query(int id,int l,int r,int pos) {
    if(l==r) return calc(pos,tr[id]);
    int mid=(l+r)/2;
    if(pos<=mid) return min(calc(pos,tr[id]),query(id*2,l,mid,pos));
    else return min(calc(pos,tr[id]),query(id*2+1,mid+1,r,pos));
}

signed main() {
    n=read(),l=read();
    for(int i=1;i<=n;i++) {
        int t1=read(),t2=read();
        s[t1]+=t2;
    }
    sum1[0]=s[0];
    for(int i=1;i<=l;i++) {
        sum1[i]=sum1[i-1]+s[i];
        sum2[i]=sum2[i-1]+i*s[i];
    }
    for(int i=0;i<=l;i++) {
        dp[i][1]=i*sum1[i]-sum2[i];
    }
        
    for(int t=2;t<=4;t++) {
        memset(k,0,sizeof k);
        memset(b,0,sizeof b);
        memset(tr,0,sizeof tr);
        k[0]=-sum1[0],b[0]=sum2[0]; update(1,0,maxn-1,0);
        for(int i=1;i<=l;i++) {
            dp[i][t]=query(1,0,maxn-1,i)+i*sum1[i]-sum2[i];
            k[i]=-sum1[i],b[i]=sum2[i]+dp[i][t-1]; update(1,0,maxn-1,i);
        }
    }
    cout<<dp[l][4]<<'\n';
    return 0;
}

P2900 [USACO08MAR] Land Acquisition G

题目链接

既然所有的土地都要买，那么我们可以考虑到，如果一块土地的宽和高都比另一块要小，那么肯定是直接并购，这一块对答案没有任何贡献。

我们先把这些给去掉，具体做法可以是，按高为第一关键字，宽为第二关键字从大到小排序，因为考虑当前这一个的高肯定是小于等于上一个的高，如果宽还比上一个小，则没有贡献，不用继续考虑。

于是，剩下的就是一个高度递减，宽度递增的矩形序列。考虑怎样制定它们的并购方案会最优。显然如果要并购，一定要挑序列中的一段区间，这样贡献答案的就只有最左边矩形的高乘上最右边矩形的宽，中间的又是没有贡献了。

设 \(f_{i}\)为前 \(i\) 个矩形的最小花费，直接写出一个 \(O\left(n^{2}\right)\) 的方程:

\[ f_{i}=\min _{j=0}^{i}\left\{f_{j}+l_{i} w_{j+1}\right\} \]

典型的斜率优化，代码如下:

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define db double
#define rg register
#define pb push_back
#define pob pop_back
#define pii pair<int,int>
#define vi vector<int>
#define fr first
#define sc second
#define endl '\n'
#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5e4+10;
const int maxm=1e6+10;

int read() {
    int f=1,x=0;
    char c;
    while(!isdigit(c)) {
        if(c=='-') f=-1;
        c=getchar();
    }while(isdigit(c)) {
        x=(x<<1)+(x<<3)+(c-'0');
        c=getchar();
    }return x*f;
}
int tr[maxm*4],k[maxn],b[maxn],dp[maxn],n;
int x[maxn],y[maxn],cnt;
struct node{
    int w,l;
}e[maxn];

bool cmp(node n1,node n2) {
    if(n1.w!=n2.w) return n1.w>n2.w;
    else return n1.l>n2.l;
}

int get(int id,int val) {
    return k[id]*val+b[id];
}

void update(int u,int l,int r,int val) {
    if(l==r) {
        if(get(val,l)<get(tr[u],l)) tr[u]=val;
        return;
    } int mid=(l+r)/2;
    if(get(val,mid)<get(tr[u],mid)) swap(val,tr[u]);
    if(get(val,l)<get(tr[u],l)) update(u*2,l,mid,val);
    else if(get(val,r)<get(tr[u],r)) update(u*2+1,mid+1,r,val);
}

int query(int u,int l,int r,int pos) {
    if(l==r) return get(tr[u],pos);
    int mid=(l+r)/2;
    if(pos<=mid) return min(get(tr[u],pos),query(u*2,l,mid,pos));
    else return min(get(tr[u],pos),query(u*2+1,mid+1,r,pos));
}

signed main() {
    n=read();
    for(int i=1;i<=n;i++) {
        e[i].w=read(),e[i].l=read();
    } sort(e+1,e+1+n,cmp);
    y[0]=-1;
    for(int i=1;i<=n;i++) {
        if(e[i].l>y[cnt]) {
            ++cnt; x[cnt]=e[i].w,y[cnt]=e[i].l;
        }
    }
    n=cnt;
    b[0]=0,k[0]=x[1]; update(1,1,maxm-1,0);
    for(int i=1;i<=n;i++) {
        dp[i]=query(1,1,maxm-1,y[i]); 
        k[i]=x[i+1],b[i]=dp[i]; update(1,1,maxm-1,i);
    }
    cout<<dp[n]<<'\n';
    return 0;
}
本文作者：BHX
本文链接：https://ma-siwei.github.io/chitose.github.io/2025/04/15/斜率优化DP/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
OI