[CEOI2004]锯木厂选址

[CEOI2004]锯木厂选址

题面描述

传送门

思路

状态转移方程

t o t tot tot为所有树都运到山下锯木厂的费用， d i s dis dis为到山下锯木厂的距离， s s s为树的重量前缀和。

F i = min ⁡ ( t o t − d i s j ∗ s j − d i s i ∗ ( s i − s j ) ) ( j &lt; i ) F_i=\min(tot-dis_j*s_j-dis_i*(s_i-s_j))(j&lt;i) Fi​=min(tot−disj​∗sj​−disi​∗(si​−sj​))(j<i)

不难理解, [ 1 , j ] [1,j] [1,j]的木头运到 j j j处锯木厂， [ j + 1 , i ] [j+1,i] [j+1,i]运到 i i i处锯木厂，剩余的运往山下锯木厂。

决策单调性

设

t o t − d i s j ∗ s j − d i s i ∗ ( s i − s j ) &gt; t o t − d i s k ∗ s k − d i s i ∗ ( s i − s k ) ( j &lt; k &lt; i ) tot-dis_j*s_j-dis_i*(s_i-s_j)&gt;tot-dis_k*s_k-dis_i*(s_i-s_k)(j&lt;k&lt;i) tot−disj​∗sj​−disi​∗(si​−sj​)>tot−disk​∗sk​−disi​∗(si​−sk​)(j<k<i)

化简

− d i s j ∗ s j + d i s i ∗ s j &gt; − d i s k ∗ s k + d i s i ∗ s k -dis_j*s_j+dis_i*s_j&gt;-dis_k*s_k+dis_i*s_k −disj​∗sj​+disi​∗sj​>−disk​∗sk​+disi​∗sk​

在未来状态 t t t，证明:

− d i s j ∗ s j + d i s t ∗ s j &gt; − d i s k ∗ s k + d i s t ∗ s k -dis_j*s_j+dis_t*s_j&gt;-dis_k*s_k+dis_t*s_k −disj​∗sj​+dist​∗sj​>−disk​∗sk​+dist​∗sk​

由 d i s t = d i s i + v a l ( v a l &lt; 0 ) dis_t=dis_i+val(val&lt;0) dist​=disi​+val(val<0)，

− d i s j ∗ s j + ( d i s i + v a l ) ∗ s j &gt; − d i s k ∗ s k + ( d i s i + v a l ) ∗ s k -dis_j*s_j+(dis_i+val)*s_j&gt;-dis_k*s_k+(dis_i+val)*s_k −disj​∗sj​+(disi​+val)∗sj​>−disk​∗sk​+(disi​+val)∗sk​

仅需证明:

v a l ∗ s j &gt; v a l ∗ s k val*s_j&gt;val*s_k val∗sj​>val∗sk​

s j &lt; s k s_j&lt;s_k sj​<sk​

证毕。

踢队头

− d i s j ∗ s j + d i s i ∗ s j &gt; − d i s k ∗ s k + d i s i ∗ s k -dis_j*s_j+dis_i*s_j&gt;-dis_k*s_k+dis_i*s_k −disj​∗sj​+disi​∗sj​>−disk​∗sk​+disi​∗sk​

d i s j ∗ s j − d i s k ∗ s k &lt; d i s i ∗ s j − d i s i ∗ s k dis_j*s_j-dis_k*s_k&lt;dis_i*s_j-dis_i*s_k disj​∗sj​−disk​∗sk​<disi​∗sj​−disi​∗sk​

c a l c ( j , k ) = d i s j ∗ s j − d i s k ∗ s k s j − s k &gt; d i s i calc(j,k)=\frac{dis_j*s_j-dis_k*s_k}{s_j-s_k}&gt;dis_i calc(j,k)=sj​−sk​disj​∗sj​−disk​∗sk​​>disi​

k k k优于 j j j

即

c a l c ( q h e a d , q h e a d + 1 ) &gt; d i s i calc(q_{head},q_{head+1})&gt;dis_i calc(qhead​,qhead+1​)>disi​

q h e a d + 1 q_{head+1} qhead+1​优于 q h e a d q_{head} qhead​，踢去 h e a d head head

维护一个 c a l c ( q h e a d , q h e a d + 1 ) &lt; d i s i calc(q_{head},q_{head+1})&lt;dis_i calc(qhead​,qhead+1​)<disi​队列

同时我们可以发现， d i s i dis_i disi​随 i i i增大而减小，那么 c a l c ( q h e a d , q h e a d + 1 ) calc(q_{head},q_{head+1}) calc(qhead​,qhead+1​)随 d i s i dis_i disi​的减小， h e a d head head不断增大，而不断减小。

因此，队列维护的应该是一个上凸壳。

踢队尾

由于维护一个上凸壳，

所以

c a l c ( q t a i l − 1 , q t a i l ) &gt; c a l c ( q t a i l , i ) calc(q_{tail-1},q_{tail})&gt;calc(q_{tail},i) calc(qtail−1​,qtail​)>calc(qtail​,i)

反之，

当

c a l c ( q t a i l − 1 , q t a i l ) ≤ c a l c ( q t a i l , i ) calc(q_{tail-1},q_{tail})\le calc(q_{tail},i) calc(qtail−1​,qtail​)≤calc(qtail​,i)

踢去队尾。

AC code

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define ll long long 
#define gc getchar()
using namespace std;
const int N=2e4+10;
inline void qr(ll &x)
{x=0;int f=1;char c=gc;while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}x*=f;
}
inline void qw(ll x)
{if(x<0)x=-x,putchar('-');if(x/10)qw(x/10);putchar(x%10+48);
}
ll dis[N],s[N],tot,f[N];
int q[N],l,r;
inline double calc(int j,int k)
{return (double)(dis[j]*s[j]-dis[k]*s[k])/(s[j]-s[k]);
}
int main()
{int n;scanf("%d",&n);ll tot=0;for(int i=1;i<=n;i++)qr(s[i]),qr(dis[i]),s[i]+=s[i-1],tot+=s[i]*dis[i];for(int i=n;i>=1;i--)dis[i]+=dis[i+1];l=1;r=1;q[1]=0;ll ans=1e10;for(int i=1;i<=n;i++){while(l<r&&calc(q[l],q[l+1])>=dis[i])++l;ans=min(ans,tot-dis[q[l]]*s[q[l]]-dis[i]*(s[i]-s[q[l]]));while(l<r&&calc(q[r],i)>=calc(q[r-1],q[r]))--r;q[++r]=i;}qw(ans);puts("");return 0;
}