编号山脚的树是1

w[i] 表示从1号到i号节点的树的总质量。

d[i] 表示第i棵树距离山脚的锯木厂的距离。

g[i] 表示从i到n棵树都运到i地的锯木厂所用的费用。

h[i] 表示从1到i棵树都运到山底锯木厂所用的费用。

f[i] 表示中间的锯木厂建设在i处所用过的最小费用。

很容易写出朴素方程  f[i] = h[i-1] + g[j] +　h[j-1] - h[i] - (w[j-1] - w[i])*d[i]

进行一下化简变换。

令t[i]=g[x]+h[x-1]

得到(t[x]-t[y])/(w[x-1]-w[y-1])>d[i]

注意当前你的i是倒着循环的，所以凸包要反着画，斜率之间的关系也因此而发生改变。

 

1 program wood(input,output); 2 var 3     h     :array[0..25000] of int64; 4     f,g   :array[0..25000] of int64; 5     w     :array[0..25000] of int64; 6     d     :array[0..25000] of int64; 7     q      :array[0..25000] of longint; 8     n        :longint; 9     answer:int64;10 procedure init;11 var12     i:longint;13 begin14     readln(n);15     for i:=n downto 1 do16         readln(w[i],d[i]);17 end;{
      init }18 procedure change();19 var20     i:longint;21 begin22     for i:=1 to n do23     begin24         w[i]:=w[i-1]+w[i];25         d[i]:=d[i-1]+d[i];26         h[i]:=h[i-1]+(w[i]-w[i-1])*d[i];27     end;28     for i:=n downto 1 do29         g[i]:=g[i+1]+(w[n]-w[i])*(d[i+1]-d[i]);30 end;{
      change }31 function K(x,y:longint):double;32 begin33     exit((g[x]+h[x-1]-g[y]-h[y-1])/(w[x-1]-w[y-1]));34 end;{
      K }35 procedure main;36 var37     i         :longint;38     head,tail:longint;39     bestK     :double;40 begin41     head:=1;42     tail:=1;43     q[1]:=n;44     f[n]:=0;45     answer:=maxlongint;46     for i:=n-1 downto 1 do47     begin48         bestK:=d[i];49         while (tail-head+1>=2)and(k(q[head+1],q[head])>=bestk) do50             inc(head);51         f[i]:=h[i-1]+g[q[head]]+h[q[head]-1]-h[i]-d[i]*(w[q[head]-1]-w[i]);52         while (tail-head+1>=2)and(k(q[tail],q[tail-1])