【bzoj1096】仓库建设——斜率优化dp

题目链接

我们用sum[i]表示前i个工厂的产品数之和，b[i]表示x[i]*p[i]的前缀和，因此第j+1~i个工厂的产品运到第i个工厂的代价就是

　　(sum[i]-sum[j])*x[i]-(b[i]-b[j])+ci[i]

最后f[i]的状态转移方程即为：

　　f[i]=f[j]+(sum[i]-sum[j])*xi[i]-(b[i]-b[j])+ci[i]

斜率式的推导过程就不写了，最后可以化成：

　　(f[j]+b[j]-f[k]-b[k])/(sum[j]-sum[k])<xi[i]-ci[i](k<j<i)

//然而刚开始最后的那个加号写成乘号导致WA了两次，要注意队列的q[0]=0（不是1！！！），还是要细心吧。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long LL;
const int maxn=1000010;
using namespace std;
LL xi[maxn],pi[maxn],ci[maxn],sum[maxn],b[maxn],f[maxn],q[maxn];
inline LL read()
{
    LL anss=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){anss=anss*10+c-48;c=getchar();}
    return anss*f;
}
inline double cal(LL a,LL bb)
{
    return 1.0*(f[a]+b[a]-f[bb]-b[bb])/(sum[a]-sum[bb]);
}
int main()
{
    int n;
    n=read();
    sum[0]=0;b[0]=0;
    for(int i=1;i<=n;i++){
        xi[i]=read();pi[i]=read();ci[i]=read();
        sum[i]=sum[i-1]+pi[i];
        b[i]=b[i-1]+xi[i]*pi[i];
    }
    int h=0,t=1;q[0]=0;f[0]=0;
    for(int i=1;i<=n;i++){
        while(h<t-1&&cal(q[h],q[h+1])<xi[i])h++;
        f[i]=f[q[h]]+(sum[i]-sum[q[h]])*xi[i]-(b[i]-b[q[h]])+ci[i];
        while(h<t-1&&cal(q[t-2],q[t-1])>cal(q[t-1],i))t--;
        q[t++]=i;
    }
    printf("%lld",f[n]);
    return 0;
}