bzoj 1096 仓库建设 —— 斜率优化DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1096

设 f[i] 为 i 作为最后一个仓库时前 i 个工厂的答案，最后的答案当然是 f[n]；

f[i] = min{ f[j] + ∑(j+1<=k<=i)p[k]*(x[i]-x[k]) + c[i] } , 1<=j<i

令 s[i] = ∑(1<=j<=i)p[j]，t[i] = ∑(1<=j<=i)p[j]*x[j]

则 f[i] = min{ f[j] + x[i]*(s[i]-s[j]) - (t[i]-t[j]) + c[i] }

移项，得到 f[j] + t[j] = x[i]*s[j] - x[i]*s[i] + t[i] - c[i] + f[i]

x[i] 单增，s[j] 单增，可以看出是要维护一个下凸包。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef double db;

typedef long long ll;

int const xn=1e6+;

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

ll s[xn],t[xn],f[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

db y(int i){return f[i]+t[i];}

db slp(int a,int b){return (y(b)-y(a))/(s[b]-s[a]);}

int main()

{

  n=rd();

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

    {

      x[i]=rd(),p[i]=rd(),c[i]=rd();

      s[i]=s[i-]+p[i]; t[i]=t[i-]+(ll)p[i]*x[i];

    }

  int hd=,tl=;

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

    {

      while(hd<tl&&slp(q[hd],q[hd+])<x[i])hd++;

      f[i]=f[q[hd]]+(ll)x[i]*(s[i]-s[q[hd]])-t[i]+t[q[hd]]+c[i];

      while(hd<tl&&slp(q[tl-],q[tl])>slp(q[tl-],i))tl--;

      q[++tl]=i;

    }

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

  return ;

}

巴特西

bzoj 1096 仓库建设 —— 斜率优化DP

最新文章

热门文章