[CEOI2004]锯木厂选址

link

试题分析

做这种题就应该去先写个暴力代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<climits>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

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

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int N=;

int w[N],n,f[N],deep[N],sum,s[N],p[N],k[N];

int calc(int l,int r){

    return (p[r]-p[l-])-deep[r]*(k[r]-k[l-]);

}

int main(){

//    freopen("5.in","r",stdin);

    memset(f,/,sizeof(f));f[]=;

    n=read();

    for(int i=;i<=n;i++) w[i]=read(),deep[i]=read();

    for(int i=n;i>=;i--) deep[i]+=deep[i+];

    n++;

    for(int i=;i<=n;i++) s[i]=w[i]*deep[i];

    for(int i=;i<=n;i++) p[i]=p[i-]+s[i];

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

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

        for(int j=;j<i;j++){

            f[i]=min(f[i],-deep[j]*k[j]-deep[i]*k[i]+deep[i]*k[j]+deep[n]*k[i]);

        }

    }

    int maxn=INT_MAX;

    for(int i=;i<=n;i++) maxn=min(maxn,f[i]);cout<<maxn-deep[n]*k[n]+p[n];

}

1

然后再把calc放在里面,把无用的东西提出去。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<climits>

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

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

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int N=;

int w[N],n,f[N],deep[N],sum,s[N],p[N],k[N];

int calc(int l,int r){

    return (p[r]-p[l-])-deep[r]*(k[r]-k[l-]);

}

int main(){

//    freopen("5.in","r",stdin);

    memset(f,/,sizeof(f));f[]=;

    n=read();

    for(int i=;i<=n;i++) w[i]=read(),deep[i]=read();

    for(int i=n;i>=;i--) deep[i]+=deep[i+];

    n++;

    for(int i=;i<=n;i++) s[i]=w[i]*deep[i];

    for(int i=;i<=n;i++) p[i]=p[i-]+s[i];

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

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

        for(int j=;j<i;j++){

            f[i]=min(f[i],-deep[j]*k[j]+deep[i]*k[j]);

        }

    }

    int maxn=INT_MAX;

    for(int i=;i<=n;i++) maxn=min(maxn,f[i]-deep[i]*k[i]+deep[n]*k[i]);cout<<maxn-deep[n]*k[n]+p[n];

}

2

然后再斜率优化一下，因为我维护的是最大值，所以维护一个上凸壳即可

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<climits>

#define int long long

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

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

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int N=;

int w[N],n,f[N],deep[N],sum,s[N],p[N],k[N],l,r,que[N],X[N],Y[N],minn=LLONG_MAX;

signed main(){

//    freopen("5.in","r",stdin);

    memset(f,/,sizeof(f));f[]=;

    n=read();

    for(int i=;i<=n;i++) w[i]=read(),deep[i]=read();

    for(int i=n;i>=;i--) deep[i]+=deep[i+];

    n++;

    for(int i=;i<=n;i++) s[i]=w[i]*deep[i];

    for(int i=;i<=n;i++) p[i]=p[i-]+s[i];

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

    l=r=,que[]=;Y[]=deep[]*k[],X[]=k[];

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

        while(l<r&&Y[que[l+]]-Y[que[l]]>=deep[i]*(X[que[l+]]-X[que[l]])) l++;

        f[i]=deep[i]*k[que[l]]-deep[que[l]]*k[que[l]];

        X[i]=k[i],Y[i]=deep[i]*k[i];

        while(l<r&&(Y[que[r]]-Y[que[r-]])*(X[i]-X[que[r]])<=(X[que[r]]-X[que[r-]])*(Y[i]-Y[que[r]])) r--;

        que[++r]=i;

    }

    for(int i=;i<=n;i++) minn=min(minn,f[i]-deep[i]*k[i]+deep[n]*k[i]);printf("%lld\n",minn-deep[n]*k[n]+p[n]);

    return ;

}