P4360 [CEOI2004]锯木厂选址

令 \(f_i\) 表示仅在 \(i\) 位置建立一个锯木厂的最小费用，\(dis_i\) 表示从山脚到 \(i\) 位置的距离，\(sum_i\) 表示从山顶到 \(i\) 位置的树的重量和，可以直接预处理出来。

那么第二个锯木厂建立在位置 \(i\) 的费用就是 \(\min\{f_j-dis_i\times(sum_i-sum_j)|j<i\}\)。

考虑两个决策点 \(j,k(j<k)\)，若 \(j\) 对于当前点更优，那么：

维护 \((sum,f)\) 的下凸包。

code:

#include<bits/stdc++.h>
using namespace std;
#define N 20005
#define Db double
#define Min(x,y)((x)<(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
#define Down(i,x,y)for(i=x;i>=(y);i--)
int sum[N],dis[N],f[N],que[N];
inline Db slope(int j,int k)
{
	return Db(f[k]-f[j])/Db(sum[k]-sum[j]);
}
int main()
{
	int n,i,mn=INT_MAX,head=1,tail=0;
	scanf("%d",&n);
	For(i,1,n)scanf("%d%d",&sum[i],&dis[i]),sum[i]+=sum[i-1];
	Down(i,n,1)dis[i]+=dis[i+1],f[0]+=dis[i]*(sum[i]-sum[i-1]);
	For(i,1,n)
	{
		f[i]=f[0]-sum[i]*dis[i];
		while(head<tail&&slope(que[head],que[head+1])<=-dis[i])head++;
		if(i>1)mn=Min(mn,f[que[head]]-dis[i]*(sum[i]-sum[que[head]]));
		while(head<tail&&slope(que[tail-1],que[tail])>=slope(que[tail],i))tail--;
		que[++tail]=i;
	}
	printf("%d",mn);
	return 0;
}