斜率优化学习笔记

首先上一道例题：

HDU3507

给你一个序列，你可以把这个序列分成若干段，每段的花费是 $(\sum _{i=1} ^k C[i])^2 +M$

考虑朴素的 $n^2$ 方程， $dp[i]=\min(dp[j]+M+(sum[i]-sum[j])^2)$

其中 $sum[i]$ 为 $C[i]$ 的前缀和。

发现这个算法的瓶颈在寻找最优的 $j$ ，如果我们可以 $O(1)$ 的找到 $j$ ，那么整个算法的时间复杂度为 $O(n)$ ，可以AC。

考虑两个数 $j_1,j_2$ ， $j_1>j_2$ ，考虑 $j_1$ 比 $j_2$ 更优的条件：

$dp[j_1]+M+(sum[i]-sum[j_1])^2<dp[j_2]+M+(sum[i]-sum[j_2])^2$

移项，此处省略1w字，得：

$dp[j_1]-dp[j_2]+sum[j_1]^2-sum[j_2]^2<2 \times sum[i] \times (sum[j_1]-sum[j_2])$

不妨设 $y(i)=dp[i]+sum[i]^2$ ， $x(i)=sum[i]$

原式化为以下形式：

$y(j_1)-y(j_2)<2 \times sum[i] \times (x(j_1)-x(j_2))$

发现这个其实类似于斜率：

$\dfrac{y(j_1)-y(j_2)}{x(j_1)-x(j_2)} < 2 \times sum[i]$

其中我们能做这样的变换，有一个重要的先决条件，即 $x(j_1)>x(j_2),j_1>j_2$

将 $x,y$ 表示在二维平面上面，如图：

用一个斜率为 $2 \times sum[i]$ 的直线去逼近，发现切点就是最佳决策，又发现 $2 \times sum[i]$ 随着 $i$ 的增大而增大，所以之前舍弃的决策点不可能成为下一步的最佳决策点，于是我们可以用一个单调队列维护决策点集合。

inline double Slope(int i,int j){
    return (double)(dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j])/(double)(sum[i]-sum[j]);
}
while (head<rear&&Slope(q[head+1],q[head])<=(double)2.00*sum[i]) head++;

如何插入元素呢，我们像凸包一样插入和删除，如图：

1 2	while (head<rear&&Slope(q[rear],q[rear-1])>=Slope(i,q[rear])) rear--; q[++rear]=i;

想学习凸包可以参考这篇博客

代码实现（还是很简短的）：

注意此代码精度有问题，你们可以把除法改成乘法试一下。

#include <bits/stdc++.h>
#define MAXN 1000005
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1ll;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3ll)+(x<<1ll)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int sum[MAXN];
int dp[MAXN],q[MAXN],head,rear;
inline double Slope(int i,int j){
    return (double)(dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j])/(double)(sum[i]-sum[j]);
}
#undef int
int main(){
#define int long long
    int n,M;
    while (~scanf("%lld%lld",&n,&M)){
        memset(sum,0,sizeof(sum));
        for (register int i=1;i<=n;++i){
            int x;
            scanf("%lld",&x);
            sum[i]=sum[i-1]+x;
        }
        memset(dp,0,sizeof(dp));
        memset(q,0,sizeof(q));
        head=1,rear=1;
        q[1]=0;
        for (register int i=1;i<=n;++i){
            while (head<rear&&Slope(q[head+1],q[head])<=(double)2.00*sum[i]) head++;
            int j=q[head];
            dp[i]=dp[j]+M+(sum[i]-sum[j])*(sum[i]-sum[j]);
            while (head<rear&&Slope(q[rear],q[rear-1])>=Slope(i,q[rear])) rear--;
            q[++rear]=i;
        }
        printf("%lld\n",dp[n]);
    }
}

图片转自csdn

注意到普通斜率优化的条件是斜率单调， $x$ 坐标单调，但是对于更一般的情况，就发现普通斜率优化会咕咕，这时候我们要使用CDQ分治优化斜率优化，可以参考这篇博客学习一下。