本文共 2245 字，大约阅读时间需要 7 分钟。

题意

山脚下有一个锯木厂,有$n$棵树,只能从山顶往山脚方向走

给出每棵树距离山脚的距离,你可在在任意位置修建两个锯木厂

求所有树运输到锯木厂的花费最小值.

考虑枚举第二个锯木厂建在$i$位置(编号越小,距离山顶越近)

定义$f[i]$表示第二个锯木厂建在$i$位置的最小花费

$dis[i]$表示运输到山脚的距离和,$tot$为一开始所有树运输到山脚的花费

$sum[i]$表示树重量的前缀和(山顶的树在前)

$f[i]=\min \{$

如果再次枚举$j$的位置复杂度是$O(n^2)$的

$f[i]=tot-di{s}_j\ast su{m}_j-di{s}_i\ast su{m}_i+di{s}_i\ast su{m}_j$

移项得到

$$di{s}_i\ast su{m}_j-f[i]+(tot-di{s}_i\ast su{m}_i)=di{s}_j\ast su{m}_j$$

把$di{s}_i$看作斜率,$su{m}_j$看作$x$,把$di{s}_j\ast su{m}_j$看作$y$

那么就是确定了斜率,求一条直线的最大截距(这样$f[i]$就是最小)

这样我们维护的就是一个上凸壳,而且$di{s}_i$斜率不断变小,所以是单调的

当$slope(q_{head},q_{head+1})$的斜率仍然大于$di{s}_i$时就不断弹出队列

这样队头就是最优值

然后因为维护的是一个上凸壳,如果把当前的点$i$加入在队尾,说明有

$slope(q_{tail-1},q_{tail})>=slope(q_{tail},i)$

不满足,就不断踢出队尾即可

#include 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;const int inf = 1e18;int sum[maxn],dis[maxn],f[maxn],n;int head = 1, tail = 0, q[maxn];int x(int i){
    return sum[i]; }int y(int i) {
    return sum[i]*dis[i]; }double slope(int i,int j){
   	return ( 1.0*y(i)-y(j) )/( 1.0*x(i)-x(j) );}signed main(){
   	cin >> n;	for(int i=1;i<=n;i++)	scanf("%lld%lld",&sum[i],&dis[i] );	for(int i=n;i>=1;i--)	dis[i] += dis[i+1];		int ans = inf, tot = 0;	for(int i=1;i<=n;i++)	tot += dis[i]*sum[i];		for(int i=1;i<=n;i++)	sum[i] += sum[i-1];		q[++tail] = 0;	for(int i=1;i<=n;i++)	{
   		while( head+1<=tail && slope( q[head],q[head+1] )>dis[i] )	head++;		int las = q[head];		f[i] = tot-dis[las]*sum[las]-dis[i]*sum[i]+dis[i]*sum[las]; 		ans = min( ans,f[i] );		while( tail-1>=head && slope( q[tail-1],q[tail] )
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116263082 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！