Eternity

Until The End

斜率优化dp/凸包优化dp

发表于 更新于 分类于 ，
本文字数： 13k 阅读时长 ≈ 12 分钟

“不可名状。”

对于一个转移方程，能够表示为：

$f[i]=Kc[i]+B$

的一次函数形式，它则可以使用斜率优化，用于解决单调队列解决不了的问题。

单调队列可以解决形如 $f[i]=f[j]+x[i]$ 形式的问题，

而斜率优化用于解决形如 $f[i]=f[j]+x[i]\times x[j]$ 之类拥有 $x[i]\times x[j]$ 形式的转移方程。

这种题可以使用：

  1. 决策单调性优化dp
  2. 斜率优化dp
  3. 高级数据结构优化dp（如李超线段树）

来解决。

例题

P2365 任务安排

朴素思想

首先应该知道，不分批并不一定是最优的，因为每个任务的完成时间规定为其所在批次的最后一个任务的完成时间。

用 $dp[i][j]$ 来表示当前第 $i$ 个工程，已经分了 $j$ 组的最小代价，用 $pret[]$ 和 $prec[]$ 数组表示两个代价的前缀和。

则有：

$dp[i,j]=\min\limits_{0\leq k<i}\{dp[k,j-1]+(s\times j+pret[i])\times (prec[i]-prec[k])\}$

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ ，不够。

费用提前计算优化

根据以往的做题经验，我们尝试把二维化成一维，即让 $dp[i]$表示前 $i$ 个任务分批执行的最小费用。

但是这样我们就不知道机器启动过几次了！

别慌，冷静分析一下你会发现，如果我们要从 $dp[j]$ 转移到 $dp[i]$ 的话，由于第 $j+1\sim i$ 都是在同一批内完成的，我们只需要把 $s$ 对 $j+1$ 后的影响补充到费用中就可以了！

$dp[i]=\min\limits_{0\leq j<i}\{dp[j]+pret[i]\times(prec[i]-prec[j])+s\times (prec[n]-prec[j])\}$

时间复杂度 $\mathcal O(n^2)$ ，这就是费用提前计算的思想。

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=5e3+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,S;
ll dp[MAXN],Tme[MAXN],Cst[MAXN];
int main()
{
    // freopen("dp-slopeopt.in","r",stdin);
    // freopen("dp-slopeopt.out","w",stdout);
    read(N,S);
    for(int i=1;i<=N;++i) read(Tme[i],Cst[i]);
    for(int i=2;i<=N;++i) Tme[i]+=Tme[i-1],Cst[i]+=Cst[i-1];
    memset(dp,0x3f,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]+Tme[i]*(Cst[i]-Cst[j])+S*(Cst[N]-Cst[j]));
    printf("%lld",dp[N]);
    return 0;
}
/*

*/

斜率优化

对于上述的转移方程而言，一共有三个会影响答案的变量：

$j,dp[j],dp[i]$

把最小值去掉，然后化简：

$dp[j]=(s+pret[i])\times prec[j]+dp[i]-pret[i]\times prec[i]-s\times prec[n]$

那么，这是一个 $dp[j]$ 关于 $prec[j]$ 的一次函数。

斜率为 $s+pret[i]$ ，截距为 $dp[i]-pret[i]\times prec[i]-s\times prec[n]$

目标是 $dp[i]$ 最小，即截距最小。

接下来，我会以我所理解的斜率优化阐述，可能不对，慎重阅读！！！

首先，做出 $x=prec[j],y=dp[j]$ 的图像。并做出相应的散点 $(prec[j],dp[j])$ 。（我们这里首先只说横坐标单调递增的情况）

对于每一次计算 $i$ 时，我们将一条斜率为 $s+pret[i]$ 的直线从 $-\inf$ 开始向上移动，对于第一个碰到的点，该点对应的截距就是 $\min\{dp[i]\}$ 。

而对于用 $\mathcal{O}(1)$ 的时间找出最小的点，我们用类似于单调队列优化里的思想维护散点组成的凸包的上下凸边即可。

对于一个点是否在凸包上，满足：

  • 该点与上一个凸包点组成直线的斜率小于当前斜率；
  • 该点与下一个凸包点组成直线的斜率大于当前斜率。

即对于 $j_1<j_2<j_3$ ，使 $j_2$ 成为凸包点的条件：

  • 如果上凸，则 $j_2$ 不可能为最优。
  • 如果下凸，且 $\frac{dp[j_2]-dp[j_1]}{prec[j_2]-prec[j_1]}<\frac{dp[j_3]-dp[j_2]}{prec[j_3]-prec[j_2]}$ 。

简单来说，对于这三个点，只要 $l_{j_1-j_2}$ 的斜率小于 $l_{j_2-j_3}$ 的斜率即可。

然后就是类似于单调队列的维护了：

  • 检查队头元素 $q[l]$ 和 $q[l+1]$ 所构成的直线斜率是否满足：$\frac{dp[q[l+1]]-dp[q[l]]}{prec[q[l+1]]-prec[q[l]]}\leq s+pret[i]$ ，如果满足，则执行 ++head ，重复该步骤。
  • 取出当前队头，更新答案。
  • 检查队尾元素 $j_1=q[r-1]$ 和 $j_2=q[r]$ ，和当前点 $j_{3}=i$ ，是否满足斜率单调递增，如果不是，则执行 --tail ，重复该步骤。
  • q[++tail]=i

完成。

AC Code 
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<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=3e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,S;
ll dp[MAXN],Tme[MAXN],Cst[MAXN];
int Q[MAXN],head,tail;
int main()
{
    // freopen("dp-slopeopt.in","r",stdin);
    // freopen("dp-slopeopt.out","w",stdout);
    read(N,S);
    for(int i=1;i<=N;++i) read(Tme[i],Cst[i]);
    for(int i=2;i<=N;++i) Tme[i]+=Tme[i-1],Cst[i]+=Cst[i-1];
    memset(dp,0x3f,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]+Tme[i]*(Cst[i]-Cst[j])+S*(Cst[N]-Cst[j]));*/
    //O(n^2)
    Q[1]=0,head=tail=1;
    for(int i=1;i<=N;++i)
    {
        while(head<tail&&(dp[Q[head+1]]-dp[Q[head]])<=(Tme[i]+S)*(Cst[Q[head+1]]-Cst[Q[head]])) ++head;
        int j=Q[head];
        dp[i]=dp[j]-(Tme[i]+S)*(Cst[j])+Tme[i]*Cst[i]+S*Cst[N];
        while(head<tail&&(dp[Q[tail]]-dp[Q[tail-1]])*(Cst[i]-Cst[Q[tail]])>=(dp[i]-dp[Q[tail]])*(Cst[Q[tail]]-Cst[Q[tail-1]])) --tail;
        Q[++tail]=i;
    }
    printf("%lld",dp[N]);
    return 0;
}
/*
5
1
1 3
3 2
4 3
2 3
1 4
*/

P3195 [HNOI2008]玩具装箱

题解

这道题看似是紫题，其实也是一道斜率优化的模板题。

令 $a[i]=sum[i]+i,b[i]=a[i]+L+1$ ，方便表示 。

推出转移方程为：

$dp[i]=dp[j]+(a[i]-b[j])^2$

然后变成点斜式：

$dp[i]-a[i]^2=2a[i]\times b[j]+dp[j]+b[j]^2$

用一次函数的方式表示：

$x=b[j]$

$y=dp[j]+b[j]^2$

$k=2a[i]$

$b=dp[i]-a[i]^2$

完成。

然后用经典的斜率优化单调推进解出即可。

注：在斜率优化里，一般为了避免除法导致的运行时错误，所以将除法提出变成乘法，但在这一次里，我还是写的除法，算是斜率优化的另一种写法。

AC Code 
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
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=5e4+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,head=1,tail=1,q[MAXN];
ll L;
db len[MAXN],dp[MAXN];
inline db calcA(int x)
{
    return len[x]+x;
}
inline db calcB(int x)
{
    return calcA(x)+L+1;;
}
inline db calcX(int x)
{
    return calcB(x);
}
inline db calcY(int x)
{
    return dp[x]+calcB(x)*calcB(x);
}
inline db slope(int a,int b)
{
    return (calcY(a)-calcY(b))/(calcX(a)-calcX(b));
}
int main()
{
    // freopen("dp-convex-hull-opt.in","r",stdin);
    // freopen("dp-convex-hull-opt.out","w",stdout);
    read(N,L);
    for(int i=1;i<=N;++i) scanf("%lf",&len[i]),len[i]+=len[i-1];
    for(int i=1;i<=N;++i)
    {
        while(head<tail&&slope(q[head],q[head+1])<2*calcA(i)) ++head;
        int j=q[head];
        dp[i]=dp[j]+(calcA(i)-calcB(j))*(calcA(i)-calcB(j));
        while(head<tail&&slope(i,q[tail-1])<slope(q[tail-1],q[tail])) --tail;
        q[++tail]=i;
    }
    printf("%lld",(ll)dp[N]);
    return 0;
}
/*
xj=lenj+j
yj=dpj+(lenj+j)^2
ki=-2(L+1-(lenj+j))
bi=dpi-(leni+i-(L+1))^2
*/

CF311B Cats Transport

多维斜率优化，推出式子。

用 $s[i]$ 表示 $\sum\limits^{i}_{k=1}t[k]$ ，则有：

$\sum_{k = j + 1}^{i}{t_{i} - t_{k}}= \sum_{k = j + 1}^{i}{t_{i}} - \sum_{k = j + 1}^{i}{t_{k}} = (i - j) t_{i} - (s[i] - s[j])$

用 $dp[i][j]$ 表示第 $i$ 个人选择了 $j$ 只猫的最小代价。然后得出斜率式：

$s[k]+dp[i-1][k]=t[j]k-jt[j]+s[j]+dp[i][j]$

$y=s[k]+dp[i-1][k],k=t[j],b=-jt[j]+s[j]+dp[i][j]$

完成，反正我是不会做的。

AC Code 
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
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=1e5+1;
const int MAXP=1e2+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,P;
ll dth[MAXN],tme[MAXN],id,cst[MAXN];
ll dp[MAXP][MAXN],Que[MAXN],sum[MAXN];
inline ll get_Y(int k,int j)
{
    return dp[j-1][k]+sum[k];
}
int main()
{
    // freopen("dp.in","r",stdin);
    // freopen("dp.out","w",stdout);
    read(N,M,P);
    for(int i=2;i<=N;++i) read(dth[i]),dth[i]+=dth[i-1];
    for(int i=1;i<=M;++i)
    {
        read(id,tme[i]);
        cst[i]=tme[i]-dth[id];
    }
    sort(cst+1,cst+1+M);
    for(int i=1;i<=M;++i) sum[i]=sum[i-1]+cst[i];
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<=P;++i) dp[i][0]=0;
    for(int j=1;j<=P;++j)
    {
        int head=0,tail=0;
        Que[0]=0;
        for(int i=1;i<=M;++i)
        {
            while(head<tail&&(get_Y(Que[head+1],j)-get_Y(Que[head],j))<=cst[i]*(Que[head+1]-Que[head])) ++head;
            int k=Que[head];
            dp[j][i]=dp[j-1][k]-cst[i]*k+sum[k]+cst[i]*i-sum[i];
            while(head<tail&&(get_Y(Que[tail],j)-get_Y(Que[tail-1],j))*(i-Que[tail])>=(get_Y(i,j)-get_Y(Que[tail],j))*(Que[tail]-Que[tail-1])) --tail;
            Que[++tail]=i;
        }
    }
    printf("%lld",dp[P][M]);
    return 0;
}
/*
4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12
*/

P3628 特别行动队

当做是我练习推式子的练习题了。发现异常好推。

令 $s[i]$ 表示为 $x$ 的前缀和，则有：

$dp[i]=as[i]^2+bs[i]+c+as[j]^2-2as[i]s[j]-bs[j]+dp[j]$

然后化成函数式表示为：

$dp[j]+as[j]^2-bs[j]=2as[i]s[j]+dp[i]-as[i]^2-bs[i]-c$

$\mathcal{END}$

AC Code 
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
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=1e6+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
ll N,a,b,c;
ll s[MAXN],dp[MAXN],val;
ll head,tail,Que[MAXN];
inline ll K(int id)
{
    return 2*a*s[id];
}
inline ll X(int id)
{
    return s[id];
}
inline ll Y(int id)
{
    return dp[id]+a*s[id]*s[id]-b*s[id];
}
inline ll B(int id)
{
    return dp[id]-a*dp[id]*dp[id]-b*dp[id]-c;
}
inline ll slope(int x,int y)
{
    return (Y(x)-Y(y))/(X(x)-X(y));
}
int main()
{
    // freopen("dp-convex.in","r",stdin);
    // freopen("dp-convex.out","w",stdout);
    read(N,a,b,c);
    Que[head=tail=1]=0;
    for(int i=1;i<=N;++i)
    {
        read(val);
        s[i]=s[i-1]+val;
        while((head<tail)&&(Y(Que[head+1])-Y(Que[head]))>(X(Que[head+1])-X(Que[head]))*K(i)) ++head;
        if(head<=tail) dp[i]=dp[Que[head]]+(s[i]-s[Que[head]])*(s[i]-s[Que[head]])*a+(s[i]-s[Que[head]])*b+c;
        while((head<tail)&&(Y(Que[tail])-Y(Que[tail-1]))*(X(i)-X(Que[tail]))<=((Y(i)-Y(Que[tail]))*(X(Que[tail])-X(Que[tail-1])))) --tail;
        Que[++tail]=i;
    }
    printf("%lld",dp[N]);
    return 0;
}
/*
f[j]+a*s[j]*s[j]-b*s[j]=2*a*s[i]*s[j]+f[i]
4 
-1 10 -20 
2 2 3 4 
*/

总结

关于 $x,y,k,b$ 的选择：

首先，明晰斜率优化是用来解决以： $dp[i]=\min/\max\{dp[j]+a[i]+b[j]+a[i]\times b[j]\}$ 的问题，当然 $a[i]$ 和 $b[j]$ 不一定存在，但是 $a[i]\times b[j]$ 一定存在。

然后，拆下 $\min/\max$ ，并将只关于 $j$ 的置于一旁：

$dp[j]+b[j]=-a[i]\times b[j]+dp[i]-a[i]$

这个时候，一次函数式就已经列出来了。

  1. 仅关于 $i$ 的项作为 $b$ ；
  2. 仅关于 $j$ 的项作为 $y$ ；
  3. 既关于 $i$ 又关于 $j$ 的项中，$i$ 项作 $k$ ，$j$ 项作 $x$ 。
  4. 其中既与 $i$ 无关，又和 $j$ 无关的常数项视作与 $i$ 同类。

依我看来，斜率优化算是 $\mathcal{dp}$ 一栏里最难的部分了。省选+会涉及，所以根据 onehui 给我定的目标，我还是不得不学。

说实话，依我而看，我的实力远远不够，后路很长，如果一起前进最后的结果终究是四分五裂。所以，也许，是时候，做出取舍。但即使如此，我也必须努力才行啊。

$\mathcal{finished\ at\ 2022.5.14}$

相关文章