设：

　　sw[i]为1..i的w之和

　　sd[i]为1到i的距离

　　cost[i]为把第一个锯木厂建在i带来的花费

　　all[i,j]为把i..j所有木头运到j所需要的花费

所以$all[i,j]=cost[j]-cost[i-1]-sw[i-1]*(sd[j]-sd[i-1])$

我们设第2个锯木厂建在i所带来的最小花费为f[i]，则$f[i]=min\{cost[j]+all[j+1,i]+all[j+1,n+1]\}$

把all化掉，最终变成$f[i]=min\{cost[n+1]-sw[j]*(sd[i]-sd[j])-sw[i]*(sd[n+1]-sd[i])\}$

这样的话，如果直接做，复杂度是$O(n^2)$的

考虑优化，我们尝试比较在i固定时，f[j1]和f[j2]的值（j1<j2）,$f[j1]-f[j2]=sw[j2]*(sd[i]-sd[j2])-sw[j1]*(sd[i]-sd[j1])$

先假设$f[j1]-f[j2]<0$，也就是j1是较优解

那么可以得到$\frac{sw[j1]*sd[j1]-sw[j2]*sd[j2]}{sw[j1]-sw[j2]}>sd[i]$

发现右端随i单增，而且左端呈现斜率的形式

那么也就是说，如果在某次i++以后，某两个j1,j2的斜率<sd[i]，就可以确定j1永远不会是最优解了

那么可以维护一个队列，保证j1<j2<j3<... ，而且j1j2 ,j2j3 ,j3j4两两间的斜率递增

这样在每次i++的时候，先从队头向后把斜率<sd[i]的踢掉，之后的队头就是这次i的最优值

然后在统计完i的答案以后，i也可以作为第一个伐木厂了，就把它按照性质从队尾插进去

　　也就是说，对于队尾的两个元素t-1和t，若t.i间斜率>t-1.t间斜率，直接把i插到队尾；

　　　　若不是，则踢掉t然后继续做（此时的t绝对不会是最优解了，因为t-1与i间斜率<t-1与t间斜率，则要么t-1比t和i都优，要么sd[i]先超过t-1与i间的斜率，然后i会优于t-1和t）

队列里只剩一个点的话就谈不来斜率了..就不做了...

然后做的时候可以把比较斜率的除法改成乘法，防止出锅

每个点最多进队一次，出队一次，所以复杂度是O(n)的

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #define LL long long int 9 using namespace std;10 const int maxn=20005;11 12 LL rd(){13 LL x=0;char c=getchar();int neg=1;14 while(c<'0'||c>'9'){ if(c=='-') neg=-1;c=getchar();}15 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();16 return x*neg;17 }18 19 int N,w[maxn],d[maxn];20 LL sw[maxn],sd[maxn],cost;21 int q[maxn],head,tail;22 23 inline bool judge1(int j1,int j2,int i){ return sw[j1]*sd[j1]-sw[j2]*sd[j2]
            
             head&&(!judge2(q[tail-1],q[tail],i))) tail--;41 q[++tail]=i; 42 }printf("%d\n",ans);43 44 return 0;45 }