斜率优化

时间复杂度 $O(n)$
用$f[i]$来表示将$i$作为第二个锯木厂的最小费用
用$j$来表示第一个锯木厂的位置
则$f[i]=min(\sum_{k=1}^{j-1}d[k]*w[k]+$

$\sum_{k=j+1}^{i-1}(d[k]-d[j])*w[k]+$

$\sum_{k=i+1}^{n}(d[k]-d[i])*w[k])$
用$sumw[i]$来表示$w[i]$的前缀和

用$sumdw[i]$来表示$d[i]*w[i]$的前缀和

则$f[i]=sumdw[j-1]+sumdw[i-1]-sumdw[j]-d[j]\times(sumw[i-1]-sumw[j])+sumdw[n]-sumdw[i]-d[i]\times(sumw[n]-sumw[i])$
移项后可得：
$y:sumdw[j-1]-sumdw[j]+d[j]*sumw[j]$
$斜率:sumw[i-1]$
$x:d[j]$
此时$d[j]$和$sumw[i-1]$都是递增的，套用斜率优化的版子即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e4,M=1e3+1e2,K=2*1e4+1e3;
const ll Max=1e18;
ll n;
ll w[K],d[K];
ll f[K];
ll q[K];
ll sumdw[K];
ll sumw[K];
//f[i]表示将i作为第二个锯木厂的最小运输费用
ll get_y(ll j)
{
    return sumdw[j-1]-sumdw[j]+d[j]*sumw[j];
}
ll get_x(ll j)
{
    return d[j];
}
signed main()
{
    cin>>n;
    for(ll i=1;i<=n;i++)cin>>w[n-i+1]>>d[n-i+1];
    for(ll i=1;i<=n;i++)d[i]+=d[i-1];
    for(ll i=1;i<=n;i++)sumdw[i]=sumdw[i-1]+w[i]*d[i];
    for(ll i=1;i<=n;i++)sumw[i]=sumw[i-1]+w[i];
    ll hh,tt;
    hh=tt=0;
    q[0]=0;
    for(ll i=1;i<=n;i++)
    {
        while(hh<tt&&(get_y(q[hh+1])-get_y(q[hh]))<=sumw[i-1]*(get_x(q[hh+1])-get_x(q[hh])))hh++;
        ll j=q[hh];
        //j是将第一个锯木厂的位置
        f[i]=sumdw[j-1]+sumdw[i-1]-sumdw[j]-d[j]*(sumw[i-1]-sumw[j])+sumdw[n]-sumdw[i]-d[i]*(sumw[n]-sumw[i]);
        while(hh<tt&&(get_y(q[tt])-get_y(q[tt-1]))*(get_x(i)-get_x(q[tt]))>=(get_y(i)-get_y(q[tt]))*(get_x(q[tt])-get_x(q[tt-1])))tt--;
        q[++tt]=i;
    }
    ll ans=Max;
    for(ll i=1;i<=n;i++)ans=min(ans,f[i]);
    cout<<ans;
}
//f[i]=sumdw[j-1]+sumdw[i-1]-sumdw[j]-d[j](sumw[i-1]-sumw[j])+sumdw[n]-sumdw[i]-d[i](sumw[n]-sumw[i])