洛谷P4360 [CEOI2004]锯木厂选址（斜率优化）

我可能根本就没有学过斜率优化……

我们设$dis[i]$表示第$i$棵树到山脚的距离，$sum[i]$表示$w$的前缀和，$tot$表示所有树运到山脚所需要的花费，$dp[i]$表示将第二个锯木厂建在$i$的最小花费

那么状态转移方程就是$$dp[i]=min\{tot-dis[j]*sum[j]-dis[i]*(sum[j]-sum[i])\}$$

然后考虑斜率优化，设$j$比$k$更优，则（一堆乱七八糟的推导之后）有$$\frac{sum[j]*dis[j]-sum[k]-dis[k]}{sum[j]-sum[k]}>dis[i]$$

那么只要考虑维护一个上凸包就可以了

 //minamoto

 #include<iostream>

 #include<cstdio>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=;

 int sum[N],dis[N],w[N],q[N],dp[N],n,h,t,tot,ans=0x3f3f3f3f;

 inline double slope(int j,int k){

     return ((sum[j]*dis[j])-(sum[k]*dis[k]))*1.0/(sum[j]-sum[k]);

 }

 inline int calc(int i,int j){

     return tot-sum[j]*dis[j]-dis[i]*(sum[i]-sum[j]);

 }

 int main(){

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

     n=read();

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

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

     for(int i=;i<=n;++i) sum[i]=sum[i-]+w[i],tot+=w[i]*dis[i];

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

         while(h<t&&slope(q[h],q[h+])>dis[i]) ++h;

         cmin(ans,calc(i,q[h]));

         while(h<t&&slope(q[t],q[t-])<slope(q[t-],i)) --t;q[++t]=i;

     }

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

     return ;

 }

巴特西

洛谷P4360 [CEOI2004]锯木厂选址（斜率优化）

最新文章

热门文章