BZOJ1096: [ZJOI2007]倉庫建設(dp+斜率優化)

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

Sample Output

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位帶符號整數。 

Source

感覺自己拿到題目還是太想當然了，連題目都沒讀完就開始xjb列方程，，

首先題目中有一條比較重要的性質

• ‘產品只能往山下運

因此第$N$個工廠一定有倉庫

這樣的話DP方程就比較好列了，$f[i]$表示在第$i$個位置安裝了倉庫且前$i$個工廠都已經安置好的最優方案

設$dis[i]$表示$i$號節點到山頂的距離，$num[i]$為第$i$個工廠儲存物品的數量，$spend[i]$為在第$i$個工廠建造倉庫的花費

我們不難列出方程

那麼$f[i]=min(f[i],\sum_{j=1}^{i-1} f[j]+Build(j,i))$

其中$Build(l,r)$為在第$r$個位置建倉庫，前一個倉庫在$l$的費用，

我們需要求的值為$\sum_{i=l+1}^{r-1}((dis[r]-dis[i])*num[i])+spend[r]$

但是這個並不好維護，因此我們把它拆開維護

設$g(x)=\sum_{i=1}^{x} -dis[i]*num[i]$

$sum(x)=\sum_{i=1}^{x} num[i]$

根據首碼和

$$Build(l,r)=dis[r]*(sum[r-1]-sum[l])+g[r-1]-g[l]+spend[r]$$

這樣的話就有20分了

考慮繼續優化，把上面的式子暴力推推推，再把只包含$i$的刪去，不難得到

$f[i]+dis[i]*num[j]=f[j]-g[j]$

把$dis[i]$看成$k$

把$num[i]$看成$x$

把$f[i]$看成$b$

把$f[j]-g[j]$看成$y$

然後就能斜率優化了。

#include<cstdio>
#include<cstring>
#include<bitset>
#include<cmath>
#include<algorithm>
#define int long long 
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N;
int dis[MAXN],num[MAXN],spend[MAXN];
int sum[MAXN],g[MAXN];//g[i]=∑dis[i]*num[i] 
int f[MAXN];
int Q[MAXN];
int Build(int l,int r)
{
    return dis[r]*(sum[r-1]-sum[l])+g[r-1]-g[l]+spend[r];
}
double X(int x){return sum[x];}
double Y(int x){return f[x]-g[x];}
double slope(int x,int y){return ( Y(y)-Y(x) ) / ( X(y) -X(x) );}
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    //freopen("b.out","w",stdout);
    #endif
    N=read();
    for(int i=1;i<=N;i++) 
        dis[i]=read(),num[i]=read(),spend[i]=read(),
        g[i]=-dis[i]*num[i],g[i]+=g[i-1],
        sum[i]=num[i],sum[i]+=sum[i-1]; 
    for(int i=1;i<=N;i++) f[i]=Build(0,i);
    int h=1,t=1;
    for(int i=1;i<=N;i++)
    {
        while(h<t&&slope(Q[h],Q[h+1])<dis[i]) h++;
        int j=Q[h];
        f[i]=min(f[i],f[j]+Build(j,i)); 
        while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i)) t--;
        Q[++t]=i;
    }
    printf("%lld",f[N]);
    return 0;
}