[BZOJ2684][CEOI2004]锯木厂选址

BZOJ权限题!

Description

从山顶上到山底下沿着一条直线种植了n棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材,树被砍倒后要运送到锯木厂。
木材只能按照一个方向运输:朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂,使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。

Input

输入的第一行为一个正整数n——树的个数(2≤n≤20 000)。树从山顶到山脚按照1,2……n标号。接下来n行,每行有两个正整数(用空格分开)。第i+1行含有:wi——第i棵树的重量(公斤为单位)和 di——第i棵树和第i+1棵树之间的距离,1≤wi ≤10 000,0≤di≤10 000。最后一个数dn,表示第n棵树到山脚的锯木厂的距离。保证所有树运到山脚的锯木厂所需要的费用小于2000 000 000分。

Output

输出只有一行一个数:最小的运输费用。

Sample Input

9
1 2
2 1
3 3
1 1
3 2
1 6
2 1
1 2
1 1

Sample Output

26

sol

首先写出(O(n^2))(DP)式,直接枚举两个锯木厂的选址(下面假设(d_i)表示(i)到锯木厂的距离)

[f_i=min{sum_{x=1}^{j}(d_x-d_j)w_x+sum_{x=j+1}^{i}(d_x-d_i)w_x+sum_{x=i+1}^{n}d_xw_x}(j<i) ]

(s_i)(w_i)的前缀和

[f_i=sum_{x=1}^{n}d_xw_x-max{d_js_j+d_i(s_i-s_j)}(j<i) ]

(k<j)(j)(k)

[d_js_j+d_i(s_i-s_j)>d_ks_k+d_i(s_i-s_k) ]

移项得

[frac{d_js_j-d_ks_k}{s_j-s_k}>d_i ]

所以这里维护一个下凸壳,即斜率递减

code

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 100005;
ll gi()
{
	ll x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
int n,q[N],hd,tl;
ll w[N],d[N],s[N],Sum,ans=1e18;
double calc(int j,int k)
{
	return (double)(d[j]*s[j]-d[k]*s[k])/(s[j]-s[k]);
}
ll count(int i,int j)
{
	return Sum-d[j]*s[j]-d[i]*(s[i]-s[j]);
}
int main()
{
	n=gi();
	for (int i=1;i<=n;i++) w[i]=gi(),d[i]=gi();
	for (int i=n;i>=1;i--) d[i]+=d[i+1];
	for (int i=1;i<=n;i++) s[i]=s[i-1]+w[i],Sum+=d[i]*w[i];
	/*
	for (int i=1;i<=n;i++)
		for (int j=i-1;j;j--)
			printf("i=%d j=%d res=%lld
",i,j,count(i,j));
	*/
	for (int i=1;i<=n;i++)
	{
		while (hd<tl&&calc(q[hd],q[hd+1])>d[i]) ++hd;
		ans=min(ans,count(i,q[hd]));
		while (hd<tl&&calc(q[tl-1],q[tl])<calc(q[tl],i)) --tl;
		q[++tl]=i;
	}
	printf("%lld
",ans);
	return 0;
}
原文地址:https://www.cnblogs.com/zhoushuyu/p/8331252.html