接上一篇博客的入门难度，我们再来看看普通难度的斜率优化。依然是题目传送门。
其实有关于斜率优化的所有题目的解题思路都是差不多的，换汤不换药罢了。
由题意，我们可得一个朴素的dp方程：f[i]=min{f[j]+Sigma((x[i]-x[k])*p[k])}+c[i] (j+1<=k<=i,0<=j<=i)
但是我们发现，这个方程的时间复杂度是O(n^3)的，这时我们可以引入前缀和数组来把k这一维优掉。
由原dp方程得：f[i]=min{f[j]+Sigma(x[i]*p[k]-x[k]*p[k])}+c[i](j+1<=k<=i,0<=j<=i)
则：f[i]=min{f[j]+x[i]*Sigma(p[k])-Sigma(x[k]*p[k])}+c[i] (j+1<=k<=i,0<=j<=i)
设a[i]=Sigma(p[k]) b[i]=Sigma(x[k]*p[k]) (1<=k<=i)
则方程可变成：f[i]=min{f[j]+x[i]*(a[i]-a[j])-(b[i]-b[j])}+c[i] (0<=j<=i)
若k<j且j的决策要比k好，则：f[j]+x[i]*(a[i]-a[j])-(b[i]-b[j])<f[k]+x[i]*(a[i]-a[k])-(b[i]-b[k])
化简，得：f[j]-f[k]+b[j]-b[k]<x[i]*(a[j]-a[k])
不等式两边同时除以(a[j]-a[k])，得：斜率g(j,k)=(f[j]-f[k]+b[j]-b[k])/(a[j]-a[k])<x[i]
因为题目所给出的x[i]是严格单调递增的，所以g(j,k)满足单调队列的单调性，可以用斜率优化该dp方程。
之后就是维护单调队列的过程了，可以参照我的上一篇博客的证明及操作过程。
附上AC代码：
#include <cstdio> using namespace std; const int maxn=1000010; long long x[maxn],p[maxn],c[maxn],a[maxn],b[maxn],f[maxn],dui[maxn],t,w; int n; long long min(long long a,long long b){ return a<b?a:b; } long long calc(int p,int q){ return (f[p]-f[q]+b[p]-b[q])/(a[p]-a[q]); } int main(void){ scanf("%d",&n); for (int i=1; i<=n; ++i){ scanf("%lld%lld%lld",&x[i],&p[i],&c[i]); a[i]=a[i-1]+p[i]; b[i]=b[i-1]+x[i]*p[i]; } dui[t=w=1]=0; for (int i=1; i<=n; ++i){ while (t<w&&calc(dui[t+1],dui[t])<x[i]) ++t; long long p=dui[t]; f[i]=(long long)f[p]+x[i]*(a[i]-a[p])-b[i]+b[p]+c[i]; while (t<w&&calc(dui[w],dui[w-1])>calc(i,dui[w])) --w; dui[++w]=i; } printf("%lld",f[n]); return 0; }
