【BZOJ】1096 [ZJOI2007]仓库建设

【算法】DP+斜率优化

【题解】状态转移方程：f[i]=min(f[j]+g(i+1,j-1))+c[i]

关键在于如何O(1)计算g(i+1,j-1)。

推导过程：http://blog.csdn.net/PoPoQQQ/article/details/40504949

当d(j,k)中j<k且k更优时，得到斜率不等式：

(f[j]-f[k]+sumpx[j]-sumpx[k])/(sump[j]-sump[k])<x[i]

于是斜率优化。

斜率优化：http://www.cnblogs.com/onioncyc/p/6113450.html

【细节】

1.是while不是if。。。

2.p[i]*x[i]*1ll。。。

3.转double运算优先度高于除法的样子。

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=;

int q[maxn],x[maxn],p[maxn],c[maxn],n;

ll f[maxn],sump[maxn],sumpx[maxn];

double calc(int j,int k)

{return (double)(f[j]-f[k]+sumpx[j]-sumpx[k])/(sump[j]-sump[k]);}//important3

ll g(int i,int j)

{return x[i]*(sump[i-]-sump[j])-(sumpx[i-]-sumpx[j]);}

int main()

{

    scanf("%d",&n);

    sump[]=sumpx[]=;

    for(int i=;i<=n;i++)

     {

         scanf("%d%d%d",&x[i],&p[i],&c[i]);

         sump[i]=sump[i-]+p[i];

         sumpx[i]=sumpx[i-]+1ll*p[i]*x[i];//important2

     }

    int head=,tail=;q[]=;f[]=;

    for(int i=;i<=n;i++)

     {

         while(head<tail&&calc(q[head],q[head+])<x[i])head++;

         f[i]=f[q[head]]+g(i,q[head])+c[i];

         while(head<tail&&calc(q[tail-],q[tail])>calc(q[tail],i))tail--;//important1

         q[++tail]=i;

     }

    printf("%lld",f[n]);

    return ;

}