[BZOJ 1096][ZJOI2007]仓库建设

題目敘述

如果想輕鬆看懂這個題解，請先了解如何使用單調隊列優化$DP$以及如何利用單調隊列實現斜率優化

假設$DP[i]$是在第$i$座工廠建設倉庫，第$1\sim i-1$座工廠選擇性建設倉庫的條件之下，保護工廠$1\sim i$的貨物的最小總花費
那麼答案就是$DP[N]$了

我們可以得到以下遞推式：
$DP[i]=\min(DP[j]+\sum_{k=j+1}^{i}(P_{k}(X_{i}-X_{k}))+C_{i},0\leq j<i)$

事實上，如果我們預處理一些前綴和
$PROD[i]=\sum_{k=1}^{i}P_{k}$
$COST[i]=\sum_{k=1}^{i}(P_{k}(X_{N}-X{k}))$

那麼以上遞推式可以變成以下形式：
$DP[i]=\min(DP[j]+(COST[i]-COST[j])-(PROD[i]-PROD[j])(X_{N}-X_{i}),0\leq j<i)$

於是我們得到了一個$O(N^{2})$的作法
當然，這樣還不夠快

將上式整理一下，我們得到：
$DP[i]=\min(-PROD[j]X_{i}+DP[j]-COST[j]+PROD[j]X_{N}+COST[i]-PROD[i]X_{N}+PROD[i]X_{i},0\leq j<i)$

令：
$a=-PROD[j]$
$b=DP[j]-COST[j]+PROD[j]X_{N}$
$c=COST[i]-PROD[i]X_{N}+PROD[i]X_{i}$
$x=X_{i}$

則上式變成$DP[i]=\min(ax+b+c,0\leq j<i)$，其中$c$是只跟$i$有關的數字，可以當作常數
因此問題就變成了給定$x$求$ax+b$的最小值 ($ax+b$在模型上為一條直線)
其中$a$和$b$都只和$j$有關，也就是每個$j$代表一條斜直線

注意到$x$是單調遞增的，斜率$a$隨著$j$變大也有單調性 (單調遞減)

因此可以直接套用單調隊列實現的斜率優化$DP$

時間複雜度：$O(N)$

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=9223372036854775807LL;
void getmin(LL &a,const LL &b){if(b<a)a=b;}
struct Deq
{
    int S[1000001],L,R;
    void Clear(){L=0,R=-1;}
    void PushBack(const int v){S[++R]=v;}
    void PopBack(){R--;}
    void PopFront(){L++;}
    int Front(const int i){return S[L+i];}
    int Back(const int i){return S[R-i];}
    int Size(){return R-L+1;}
}DEQ;
struct Factory
{
    LL X,P,C;
}F[1000001];
int N;
LL DP[1000001],PROD[1000001],COST[1000001];
LL GetA(const int i){return -PROD[i];}
LL GetB(const int i){return DP[i]-COST[i]+PROD[i]*F[N].X;}
double GetX(const int i1,const int i2){return (double)(GetB(i1)-GetB(i2))/(GetA(i2)-GetA(i1));}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    for(int i=1;i<=N;i++)scanf("%lld%lld%lld",&F[i].X,&F[i].P,&F[i].C);
    PROD[0]=COST[0]=0LL;
    for(int i=1;i<=N;i++)
    {
        PROD[i]=PROD[i-1]+F[i].P;
        COST[i]=COST[i-1]+F[i].P*(F[N].X-F[i].X);
    }
    DP[0]=0LL;
    DEQ.Clear();
    DEQ.PushBack(0);
    for(int i=1;i<=N;i++)
    {
        DP[i]=INF;
        //DP[i] = DP[j]+(COST[i]-COST[j])-(PROD[i]-PROD[j])*(F[N].X-F[i].X)
        //DP[j]+COST[i]-COST[j]-PROD[i]*X[N]+PROD[i]*X[i]+PROD[j]*X[N]-PROD[j]*X[i]
        //-PROD[j]*X[i]+DP[j]-COST[j]+PROD[j]*X[N]+COST[i]-PROD[i]*X[N]+PROD[i]*X[i]
        //A=-PROD[j],B=DP[j]-COST[j]+PROD[j]*X[N]
        while(DEQ.Size()>=2&&GetX(DEQ.Front(0),DEQ.Front(1))<=F[i].X)DEQ.PopFront();
        DP[i]=GetA(DEQ.Front(0))*F[i].X+GetB(DEQ.Front(0))+COST[i]-PROD[i]*F[N].X+PROD[i]*F[i].X+F[i].C;
        while(DEQ.Size()>=2&&GetX(DEQ.Back(1),DEQ.Back(0))>=GetX(DEQ.Back(0),i))DEQ.PopBack();
        DEQ.PushBack(i);
    }
    printf("%lld\n",DP[N]);
    return 0;
}