BZOJ 1096 [ZJOI2007]仓库建设：斜率优化dp

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

题意：

　　有n个工厂，从左往右排成一排，分别编号1到n。

　　每个工厂里有p[i]件产品，到1号工厂的距离为x[i]，在此处建一个仓库的花费为c[i]。

　　现在你需要建造一些仓库，使得所有产品都被运送到仓库中来。

　　产品只能从左往右运输。每一件产品运输一个单位距离的花费为1。

　　问你最小总花费（运输费 + 建仓库花费）。

题解：

　　表示状态：

　　　　dp[i]表示在工厂i建了一个仓库，并且仓库1 to i中的产品都已经被运到仓库中了，此时的最小总花费。

　　找出答案：

　　　　ans = dp[n]

　　　　因为无论如何都必须在工厂n处建一个仓库。

　　如何转移：

　　　　dp[i] = min dp[j] + ∑(p[k]*(x[i]-x[k])) + c[i]

　　　　(j < i, k = j+1 to i)

　　　　定义前缀和数组：sp[i] = ∑ p[j], s[i] = ∑(x[j]*p[j])

　　　　(j = 1 to i)

　　　　则原转移方程可化简为：

　　　　　　dp[i] = min dp[j] + x[i]*(sp[i]-sp[j]) - s[i] + s[j] + c[i]

　　边界条件：

　　　　dp[0] = 0

　　斜率优化：

　　　　设j < k，且k的决策更优。

　　　　则有：dp[j] + x[i]*(sp[i]-sp[j]) + s[j]> dp[k] + x[i]*(sp[i]-sp[k]) + s[k]

　　　　整理得：(dp[j]+s[j]-dp[k]-s[k]) / (sp[j]-sp[k]) < x[i]

　　　　（注意：因为sp[j]-sp[k]<0，所以除过来之后不等式要变号）

　　　　所以slope(i,j) = (dp[i]+s[i]-dp[j]-s[j]) / (sp[i]-sp[j])

　　　　由于x[i]递增，所以用单调队列维护下凸壳即可。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 1000005

 #define INF 1000000000

 using namespace std;

 int n;

 int q[MAX_N];

 long long x[MAX_N];

 long long p[MAX_N];

 long long c[MAX_N];

 long long s[MAX_N];

 long long dp[MAX_N];

 void read()

 {

     cin>>n;

     memset(s,,sizeof(s));

     memset(p,,sizeof(p));

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

     {

         cin>>x[i]>>p[i]>>c[i];

         s[i]=s[i-]+x[i]*p[i];

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

     }

 }

 inline double slope(int i,int j)

 {

     return (double)(dp[i]+s[i]-dp[j]-s[j])/(p[i]-p[j]);

 }

 void work()

 {

     int l=,r=;

     q[]=,dp[]=;

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

     {

         while(l<r && slope(q[l],q[l+])<=x[i]) l++;

         dp[i]=dp[q[l]]+x[i]*(p[i]-p[q[l]])-s[i]+s[q[l]]+c[i];

         while(l<r && slope(q[r],i)<slope(q[r-],q[r])) r--;

         q[++r]=i;

     }

     cout<<dp[n]<<endl;

 }

 int main()

 {

     read();

     work();

 }

巴特西

BZOJ 1096 [ZJOI2007]仓库建设：斜率优化dp

最新文章

热门文章