Steven_Meng's Blog

首先上一道例题：

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))$

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

$\frac{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++;

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

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分治优化斜率优化，可以参考这篇博客学习一下。