就当是斜率优化入门啦。
令 (f_i) 表示仅在 (i) 位置建立一个锯木厂的最小费用，(dis_i) 表示从山脚到 (i) 位置的距离，(sum_i) 表示从山顶到 (i) 位置的树的重量和。可以直接预处理出来。
那么第二个锯木厂建立在位置 (i) 的费用就是 (min{f_j-dis_i imes(sum_i-sum_j)|j<i})。
考虑两个决策 (j,k(j<k))，若 (j) 比 (k) 优，那么：
[f_j-dis_i imes(sum_i-sum_j)<f_k-dis_i imes(sum_i-sum_k)
]
[f_j-f_k<dis_i imes(sum_k-sum_j)
]
[dfrac{f_j-f_k}{sum_k-sum_j}<dis_i
]
[dfrac{f_k-f_j}{sum_k-sum_j}>-dis_i
]
我们用单调队列维护 ((sum,f)) 的下凸壳。
如图，新加入一个决策点 (H) 后，原先在下凸壳中的决策点 (F,G) 一定没有用了。
为什么呢？拿 (F) 作为例子，如果 (F) 比 (E) 要优，即 (EF) 的斜率小于 (-dis_i)，那么 (FH) 的斜率肯定也小于 (-dis_i)，此时 (H) 比 (F) 要优。
也就是说 (E) 和 (H) 在任意一个位置时更优的那个不劣于 (F) 和 (G)。
这部分是弹队尾。
由于 (-dis_i) 对于当前转移是个定值且随着 (i) 的增大单调不减，所以当某个时刻最前面的决策点不优了，它就再也不可能唯一最优了。
这部分是弹队首。
时间复杂度 (Oleft(n ight))。
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;
}
总结一下大概就是：一边是与决策点无关的东西，另一边是与仅决策点有关的斜率形式。凸壳方向看定值单调性，不等式乘除负数注意变号。