【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

题解

斜率优化大火题

很容易想到\(O(n^{2})\)暴力枚举建在哪里

然后推一下式子

很容易搞出斜率优化

然后没了。。。。（我是真的懒得手撸公式了。。。）

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

using namespace std;

#define MAX 21000

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

int h,t,Q[MAX];

int f[MAX],n,w[MAX],dis[MAX],s[MAX],cc[MAX],ans=2*(1e9);

int calc(int i,int j)//在i位置和j位置建造锯木厂

{

	return s[n]-(w[i]-w[j])*(cc[n]-cc[i])-w[j]*(cc[n]-cc[j]);

}

double count(int j,int k)

{

	return 1.0*(1.0*w[j]*cc[j]-1.0*w[k]*cc[k])/(w[j]-w[k]);

}

int main()

{

	n=read();

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

	for(int i=1;i<=n;++i)f[i]=2*(1e9),cc[i]=cc[i-1]+dis[i-1];

	for(int i=1;i<=n;++i)s[i]=s[i-1]+w[i-1]*dis[i-1];

	/*

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

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

			ans=min(ans,f[i]=min(f[i],s[n]-(w[i]-w[j])*(cc[n]-cc[i])-w[j]*(cc[n]-cc[j])));

	*/

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

	{

		while(h<t&&count(Q[h],Q[h+1])<=cc[i])h++;

		int j=Q[h];

		ans=min(ans,f[i]=calc(i,j));

		while(h<t&&count(Q[t-1],Q[t])>=count(Q[t-1],i))t--;

		Q[++t]=i;

	}

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

	return 0;

}