接上一篇博客的入門難度，我們再來看看普通難度的斜率優化。依然是題目傳送門。

其實有關于斜率優化的所有題目的解題思路都是差不多的，換湯不換藥罷了。

由題意，我們可得一個樸素的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;}