P4360 [CEOI2004]锯木厂选址

---

这™连dp都不是

\(f_i\)表示第二个锯木厂设在\(i\)的最小代价

枚举1号锯木厂

\(f_i=min_{0<=j<i}(\sum_{i=1}^{n}w_id_i-D_jW_j-D_iW_i+D_iW_j)\)

D为距离后缀和，W为重量前缀和

\(f_i=min_{0<=j<i}(D_iW_j-D_jW_j)+\sum_{i=1}^{n}w_id_i-D_iW_i\)

\(X=D_i,K=W_j,B=-D_jW_j\)

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define il inline

#define rg register

#define vd void

#define sta static

typedef long long ll;

il int gi(){

    rg int x=0,f=1;rg char ch=getchar();

    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*f;

}

struct line{int k,b;};

double operator *(const line&a,const line&b){return(double)(a.b-b.b)/(b.k-a.k);}

line que[20100];

int w[20100],d[20100];

int s[20100],S[20100];

il int get(line&a,int x){return a.k*x+a.b;}

main(){

#ifdef xzz

    freopen("4360.in","r",stdin);

    freopen("4360.out","w",stdout);

#endif

    int n=gi();

    for(rg int i=1;i<=n;++i)w[i]=gi(),d[i]=gi();

    for(rg int i=n;i;--i)d[i]+=d[i+1];

    for(rg int i=1;i<=n;++i)s[i]=w[i]*d[i];

    for(rg int i=n;i;--i)S[i]=S[i+1]+s[i];

    for(rg int i=1;i<=n;++i)w[i]+=w[i-1];

    int hd=0,tl=0,ans=2e9;

    que[tl++]=(line){0,0};

    for(rg int i=1;i<=n;++i){

        while(tl-hd>1&&get(que[hd],d[i])>get(que[hd+1],d[i]))++hd;

        ans=std::min(ans,get(que[hd],d[i])+S[1]-w[i]*d[i]);

        line x=(line){w[i],-w[i]*d[i]};

        while(tl-hd>1&&x*que[tl-1]>que[tl-1]*que[tl-2])--tl;

        que[tl++]=x;

    }

    printf("%lld\n",ans);

    return 0;

}