BZOJ 3437: 小P的牧场

时间：2022-12-07 12:29:44

传送门

显然考虑 $dp$，设 $f[i]$ 表示前 $i$ 个牧场都被控制的最小代价

那么枚举所有 $j<i$ ，$f[i]=f[j]+val[i][j]+A[i]$

$val[i][j]$ 表示控制站从 $i$ 一直控制到 $j+1$ 需要的代价

考虑怎么算这个东西，设 $S[i]=\sum _{j=1}^{i}B[j]$，$T[i]=\sum _{j=1}^{i}(B[j]*j)$

那么 $val[i][j]=(S[i]-S[j])*i-(T[i]-T[j])$

然后直接展开斜率优化就好了

第一次用叉积维护凸包，快了一倍

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

typedef long double ldb;

inline int read()

{

    register int x=,f=; static char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e6+;

int n,A[N],B[N];

ll S[N],T[N],f[N];

inline ll X(int i) { return S[i]; }

inline ll Y(int i) { return f[i]+T[i]; }

inline ll calc(int i,int j) { return f[i]=f[j]+(S[i]-S[j])*i-(T[i]-T[j])+A[i]; }

inline ll Cross(ll xa,ll ya,ll xb,ll yb) { return xa*yb-xb*ya; }

int Q[N],l=,r=;

int main()

{

    n=read();

    for(int i=;i<=n;i++) A[i]=read();

    for(int i=;i<=n;i++) B[i]=read(),S[i]=S[i-]+B[i];

    for(int i=;i<=n;i++) T[i]=T[i-]+1ll*B[i]*i;

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

    {

        while( l<r && calc(i,Q[l])>=calc(i,Q[l+]) ) l++;

        int j=Q[l]; f[i]=calc(i,j);

        while( l<r &&

            Cross( X(Q[r])-X(Q[r-]),Y(Q[r])-Y(Q[r-]) , X(i)-X(Q[r-]),Y(i)-Y(Q[r-]) ) <= ) r--;

        Q[++r]=i;

    }

    printf("%lld",f[n]);

    return ;

}

相关文章