斜率优化 学习笔记

前置知识

会 $\texttt{DP}$。
会单调队列
斜率公式 $k=\dfrac{y_{2}-y_{1}}{x_{2}-x_{1}}$。

斜率优化 DP

首先可以斜率优化的通常有如下式子：

$dp_{i}=\min/\max\{a_{i}\times b_{j}+c_{i}+d_{j}+C\}\,\,\,\,\,\,\,\,\,\,\,(j<i)$

有如下约定：

$C$，$c_{i}$，$d_{i}$（之一）可能不存在，主要是 $a_{i}\times b_{j}$（没有 $a_{i}\times b_{j}$ 的叫单调队列优化）
$a_{i}$，$b_{j}$，$c_{i}$，$d_{j}$ 表示只与 $i$ 或 $j$ 有关的函数。
$C$ 表示常数。

如果直接暴力时间复杂度为 $O(n^{2})$，不够优，于是考虑优化。

将式子中可以提取的东西先提出来：

$dp_{i}=\min/\max\{a_{i}\times b_{j}+d_{j}\}+c_{i}+C\,\,\,\,\,\,\,\,\,\,\,(j<i)$

先去掉 $\min/\max$（下文默认 $j<i$）。

$dp_{i}=a_{i}\times b_{j}+d_{j}$

考虑如果存在 $j1,j2$ 使得 $j2$ 优于 $j1$ 会怎么样（下文默认式子都为 $\max$）。

$a_{i}\times b_{j1}+d_{j1}<a_{i}\times b_{j2}+d_{j2}\\ a_{i}\times (b_{j1}-b_{j2})<d_{j2}-d_{j1}\\ -a_{i}>\dfrac{d_{j2}-d_{j1}}{b_{j2}-b_{j1}}$

然后可以令

$k_{0}=-a_{i}$，$x_{x}=b_{x}$，$y_{x}=d_{x}$。

于是式子变成了

$k_{0}>\dfrac{y_{j2}-y_{j1}}{x_{j2}-x_{j1}}$

注意需要保证 $x_{j2}>x_{j1}$。

可以发现这个东西非常像斜率式。

将决策点 $X,Y$ 丢进平面。

假设有三个决策点组成点 $A,B,C$。

$A-B$ 斜率为 $k_{1}$，$B-C$ 斜率为 $k_{2}$。

当 $k_{1}>k_{2}$ 时

$k_{0}>k_{1}$ 时，$B$ 优于 $A$，反之 $A$ 优于 $B$。
$k_{0}>k_{2}$ 时，$C$ 优于 $B$，反之 $B$ 优于 $C$。

有三种情况：

$k_{0}>k_{1}>k_{2}$，$C$ 优于 $B$ 优于 $A$。
$k_{1}>k_{0}>k_{2}$，$A$ 和 $C$ 优于 $B$。
$k_{1}>k_{2}>k_{0}$，$A$ 优于 $B$ 优于 $C$。

综上所述，$B$ 永远不会成为决策点。

不难发现，可能成为决策点的点形成了下凸壳：

当 $k_{1}<k_{2}$ 时

同上，会形成一个上凸壳。

考虑如何维护答案。

下文默认下凸壳。

假设平面上已经维护了一个凸壳，现在需要知道 $dp_{i}$，假设 $i$ 对应的斜率 $k_{i}$ 是图中的紫线。

不难发现答案即为 $4$ 号点：

设维护出凸包的点集为 $\big\{(x_{i},y_{i})\big\}(i\in[1,m])$，$m$ 为集合大小。

由于凸壳的性质，这些点满足：$\dfrac{y_{i}-y_{i+1}}{x_{i}-x_{i+1}}<\dfrac{y_{j}-y_{j+1}}{x_{j}-x_{j+1}}$，其中 $i<j$，$i$ 和 $j\in[1,m)]$，通俗的讲就是前面的斜率小于后面的斜率。

考虑单调队列维护。

先算出 $i$ 点的 $k_{0}$。

1	int k0=...;

用暴力的方法找到决策点，不同于暴力的是不符合条件的会被直接弹出。

//           <=
while(l<r&&k0>=k(q[l],q[l+1])) l++;
// 其中 k 表示计算斜率
int j=q[l];// 找到决策点
dp[i]=...;// 更新

在插入新的决策点时，要先将不符合凸性的点弹出队。

1
2
3

//                       <=
while(l<r&&k(q[r],q[r-1])>=k(i,q[r-1])) r--;// 弹出不符合单调性的点
q[++r]=i;// 将 i 入队

这样斜率优化 $\texttt{DP}$ 就做好了，将 $O(n^{2})$ 优化为 $O(n)$。

注意事项：

有时将除法写成乘法以保证精度；
注意初值，从 $0$ 号点（也就是从头）转移有时要提前在凸壳里加入 $\{0,0\}$ 等初值；
加点和统计答案是两个不同的事件，不是所有题目都统计完就加点；
注意要维护严格凸的凸壳，而不是下面这样（共线）：

例题

P3628

思路在代码里。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,c;
int x[1000002];
int s[1000002];
int l,r;
int q[1000002];
int dp[1000002];
int X(int x)
{
    return s[x];
}
int Y(int x)
{
    return dp[x]+a*s[x]*s[x]-b*s[x];
}
double k(int x,int y)
{
    return 1.0*(Y(x)-Y(y))/(X(x)-X(y));
}
signed main()
{
    // dp[i] 表示以 i 为某一队的结尾所能获得的最大价值
    // dp[i]=max{dp[j]+a*(s[i]-s[j])^2+b*(s[i]-s[j])+c} (j<i)
    // s 表示前缀和
    // dp[i]=max{dp[j]+a*s[i]^2-2*a*s[i]*s[j]+a*s[j]^2+b*s[i]-b*s[j]+c}
    // dp[i]=max{dp[j]-2*a*s[i]*s[j]+a*s[j]^2-b*s[j]}+a*s[i]^2+b*s[i]+c
    // 若 j2 优于 j1，则
    // dp[j1]-2*a*s[i]*s[j1]+a*s[j1]^2-b*s[j1]<dp[j2]-2*a*s[i]*s[j2]+a*s[j2]^2-b*s[j2]
    // 2*a*s[i]*(s[j2]-s[j1])<(dp[j2]+a*s[j2]^2-b*s[j2])-(dp[j1]+a*s[j1]^2+b*s[j1])
    // 2*a*s[i]<((dp[j2]+a*s[j2]^2-b*s[j2])-(dp[j1]+a*s[j1]^2+b*s[j1]))/(s[j2]-s[j1])
    // 保证 s[j2]>s[j1]
    // 令 X[x]=s[x],Y[x]=dp[x]+a*s[x]^2-b*s[x],k0=2*a*s[i]
    // k0<(Y[j2]-Y[j1])/(X[j2]-X[j1])
    // 维护上凸包
    cin>>n>>a>>b>>c;
    for(int i=1;i<=n;++i) cin>>x[i];
    for(int i=1;i<=n;++i) s[i]=s[i-1]+x[i];
    l=0;r=0;
    for(int i=1;i<=n;++i)
    {
        int k0=2*a*s[i];
        while(l<r&&k0<=k(q[l],q[l+1])) l++;
        int j=q[l],S=s[i]-s[j];
        dp[i]=dp[j]+a*S*S+b*S+c;
        while(l<r&&k(q[r],q[r-1])<=k(i,q[r-1])) r--;
        q[++r]=i;
    }
    cout<<dp[n];
    return 0;
}