BZOJ 1096 [ZJOI2007]倉庫建設 動态規劃+斜率優化

Description

　　L公司有N個工廠，由高到底分布在一座山上。如圖所示，工廠1在山頂，工廠N在山腳。由于這座山處于高原内

陸地區（幹燥少雨），L公司一般把産品直接堆放在露天，以節省費用。突然有一天，L公司的總裁L先生接到氣象

部門的電話，被告知三天之後将有一場暴雨，于是L先生決定緊急在某些工廠建立一些倉庫以免産品被淋壞。由于

地形的不同，在不同工廠建立倉庫的費用可能是不同的。第i個工廠目前已有成品Pi件，在第i個工廠位置建立倉庫

的費用是Ci。對于沒有建立倉庫的工廠，其産品應被運往其他的倉庫進行儲藏，而由于L公司産品的對外銷售處設

置在山腳的工廠N，故産品隻能往山下運（即隻能運往編号更大的工廠的倉庫），當然運送産品也是需要費用的，

假設一件産品運送1個機關距離的費用是1。假設建立的倉庫容量都都是足夠大的，可以容下所有的産品。你将得到

以下資料：1：工廠i距離工廠1的距離Xi（其中X1=0）;2：工廠i目前已有成品數量Pi;:3：在工廠i建立倉庫的費用

Ci;請你幫助L公司尋找一個倉庫建設的方案，使得總的費用（建造費用+運輸費用）最小。

Input

　　第一行包含一個整數N，表示工廠的個數。接下來N行每行包含兩個整數Xi, Pi, Ci, 意義如題中所述。

Output

　　僅包含一個整數，為可以找到最優方案的費用。

Sample Input

3

0 5 10

5 3 100

9 6 10

Sample Output

32

HINT

在工廠1和工廠3建立倉庫，建立費用為10+10=20，運輸費用為(9-5)*3 = 12，總費用32。如果僅在工廠3建立倉庫，建立費用為10，運輸費用為(9-0)*5+(9-5)*3=57，總費用67，不如前者優。

【資料規模】

對于100%的資料， N ≤1000000。 所有的Xi, Pi, Ci均在32位帶符号整數以内，保證中間計算結果不超過64位帶符号整數。

​​傳送門​​

考慮一個工廠，可以建倉庫或者不建倉庫搬到後面的某個倉庫裡；

用f[i]表示i工廠建立倉庫，前u個倉庫的成品都搬運完畢的最小花費。

那麼枚舉一個j，假設(j+1)~i都沒有建過倉庫，

根據貪心的思想我們知道(j+1)~i肯定都運到i工廠去了，

那麼f[i]=f[j]+(j+1)~(i-1)都運到i的費用cost[j+1..i]+C[i]

其中，

cost[j+1..i]=p[j+1]*(x[i]-x[j+1])+p[j+2]*(x[i]-x[j+2])+……+p[i-1]*(x[i]-x[i-1])

            =x[i]*(p[j+1]+p[j+2]+……+p[i-1])-p[j+1]*x[j+1]-……-p[i-1]*x[i-1]

對p作字首和sump，對p*x作字首和sumpx，那麼

cost[j+1..i]=x[i]*sump[j+1..i-1]-sumpx[j+1..i-1]

也就是說，

這就得到了一個O(N^2)的算法。

接下來就是一個普通的斜率優化……

直接用double比較斜率竟然過了= =

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int 
  N=1000005;
int n,Q[N];
ll x[N],P[N],C[N];
ll sump[N],sumpx[N];
ll f[N];
double xl(int j,int k){
  return (double)(f[j]-f[k]+sumpx[j]-sumpx[k])/(double)(sump[j]-sump[k]);
}
ll ANS(int i,int j){
  return f[j]+C[i]+x[i]*(sump[i-1]-sump[j])-(sumpx[i-1]-sumpx[j]);
}
int main(){
  scanf("%d",&n);
  sump[0]=sumpx[0]=0LL;
  for (int i=1;i<=n;i++)
    scanf("%lld%lld%lld",&x[i],&P[i],&C[i]),
    sump[i]=sump[i-1]+P[i],
    sumpx[i]=sumpx[i-1]+P[i]*x[i];
  memset(f,100,sizeof(f));
  f[0]=0,Q[1]=0;
  int head=1,tail=1;
  for (int i=1;i<=n;i++){
    while (head<tail && ANS(i,Q[head])>ANS(i,Q[head+1])) head++;
    f[i]=ANS(i,Q[head]);
    while (head<tail && xl(Q[tail],i)<xl(Q[tail-1],Q[tail])) tail--;
    Q[++tail]=i;
  }
  printf("%lld\n",f[n]);
  return 0;
}