【BZOJ】1096 [ZJOI2007]仓库建设 dp+斜率优化

接上一篇博客的入门难度，我们再来看看普通难度的斜率优化。依然是题目传送门。

其实有关于斜率优化的所有题目的解题思路都是差不多的，换汤不换药罢了。

由题意，我们可得一个朴素的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;}