对于这样一类方程
\(dp_i=\min \limits_{j=1}^{i-1}(dp_j-a_ic_j)\)，其中 \(a,c\) 都为正整数且递增：
如果直接计算，时间复杂度为 \(\mathcal{O}(N^2)\)。
使用斜率优化，可以将时间复杂度将为 \(\mathcal{O}(N)\)。
在学习本节之前，请先学会单调队列，还要知道在平面直角坐标系中，斜率越小，直线（线段）越平；斜率越大，直线（线段）越陡。
建模
我们将方程变形一下。去掉 \(\min\) 和移项，得到：
\(dp_j=a_ic_j+dp_i\)。
设 \(y=dp_j,k=a_i,x=c_j,b=dp_i\)，得到：
\(y=kx+b\)。
我们称 \(k\) 为斜率，\(b\) 为截距。可以发现，最小的截距就是我们要求的 \(dp_i\)。
求一个 \(dp_i\)
假设我们已经求出了 \(dp_1 \sim dp_{i-1}\)。我们将这 \(i-1\) 个点的 \(x,y\) 坐标画到坐标系上。假设这些点的位置如下图。
因为 \(c\) 数组递增，所以每个点的 \(x\) 坐标递增，位置依次向右。
接下来，我们将斜率 \(k(a_i)=1\) 代入，生成直线：
\(b\) 值即为直线与 \(y\) 轴交点的 \(x\) 坐标。在上图中，点 \(2\) 的斜率最小。
假设我们再加入点 \(4\)，图像如下：
此时，斜率为任意正整数时，\(4\) 的截距一定都比 \(3\) 的截距小，因此我们删除点 \(3\)。
我们再将每个点顺序连接：
然后删除点 \(3\)：
可以发现，这些点组成了下凸壳，而点 \(3\) 形成了上凸壳而被删除了。
所以在求 \(dp_i\) 时，我们只需要将斜率 \(a_i\) 代入，在这些有用的点中找截距最小的点即可。
求所有 \(dp_i\)
刚才求出一个 \(dp_i\) 的时间复杂度为 \(\mathcal{O}(N)\)，总时间复杂度依然为 \(\mathcal{O}(N^2)\)。如何优化？
注意条件中 \(a\) 数组也是递增的。在斜率逐渐递增时，能取到最小值的点是逐渐向右的。
比如上图的斜率为 \(1\)，如果把斜率增加到 \(5\)，则变成下图：
此时点 \(4\) 变为最优点。
因此，我们可以用单调队列来维护有用的点。如果新加的点与队尾的点不满足下凸壳，则弹出队尾。那么什么时候该弹出队头呢？
可以发现，最优点与其左侧点组成线段的斜率一定是小于 \(a_i\) 的，最优点与其右侧点组成线段的斜率一定是大于 \(a_i\) 的。如上面斜率为 \(1\) 的图中，最优点是 \(2\)，线段 \(1 \to 2\) 的斜率小于 \(1\)，线段 \(2 \to 4\) 的斜率大于 \(1\)。
因此，如果队列中前两点组成线段的斜率小于等于 \(a_i\)，我们就把队头弹掉。满足条件后，队头的点即为最优点。
单调队列的时间复杂度为 \(\mathcal{O}(N)\)。
例题
给出两个序列 \(a,c\)，保证这两个序列中的元素递增。求出另一个序列 \(dp\)，使得：
\(dp_i=\min \limits_{j=1}^{i-1}(dp_j+a_ic_j)\)。
特别的，\(dp_1=0\)。
\(1 \le N \le 10^6,1 \le a_i,c_i \le 3 \times 10^6\)，最后答案不会小于 \(9 \times 10^{18}\)。
我们用 \(X(a)\) 表示 \(a\) 点的 \(x\) 坐标，\(Y(a)\) 表示 \(a\) 点的 \(y\) 坐标。计算斜率时会用到小数，容易有精度错误，因此我们改用乘法。用 \(slope1(a,b)\) 表示线段 \(ab(a<b)\) 斜率的分子，\(slope2(a,b)\) 表示线段 \(ab(a<b)\) 斜率的分母，\(cmp1(a,b,k)\) 判断线段 \(ab\) 的斜率是否小于 等于 \(k\)，\(cmp2(a,b,c,d)\) 判断线段 \(ab\) 的斜率是否大于等于线段 \(cd\) 的斜率。
最后代码如下。
#include<cstdio>
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
typedef long long ll;
const int N=1e6+5;
int a[N],c[N],n,q[N],h,t;
ll dp[N];
ll X(int x){
return c[x];
}
ll Y(int x){
return dp[x];
}
ll slope1(int x,int y){
return Y(y)-Y(x);
}
ll slope2(int x,int y){
return X(y)-X(x);
}
bool cmp1(int x,int y,int k){
/*slope1(x,y)/slope2(x,y)<=k*/
/*slope1(x,y)<=k*slope2(x,y)*/
return slope1(x,y)<=k*slope2(x,y);
}
bool cmp2(int x,int y,int e,int f){
/*slope1(x,y)/slope2(x,y)>=slope1(e,f)/slope2(e,f)*/
/*slope1(x,y)*slope2(e,f)>=slope1(e,f)*slope2(x,y)*/
return slope1(x,y)*slope2(e,f)>=slope1(e,f)*slope2(x,y);
}
int main(){
int i,j;
scanf("%d",&n);
h=t=1;
UP(i,1,n){
scanf("%d%d",a+i,c+i);
/*弹掉队头斜率<=a[i]的*/
while(h<t&&cmp1(q[h],q[h+1],a[i])){
++h;
}
j=q[h];
/*此时j即为最优点*/
dp[i]=dp[j]-1ll*a[i]*c[j];
/*弹掉 队尾两点线段斜率>=线段(队尾点->i)斜率的点*/
while(h<t&&cmp2(q[t-1],q[t],q[t],i)){
--t;
}
q[++t]=i;
printf("%lld%c",dp[i]," \n"[i==n]);
}
return 0;
}