斜率优化DP $O(nlog(n))$

令 sumD[i]第i个树到1号树的距离的前缀和。sumW[i]表示前i个数的重量总和
sumDW[i]表示第 i 个数到1号树的 距离重量 的累加和
DP: f[i][k]表示锯断i个树，花费k个锯木厂的最小花费。 最后我们要求的就是 f[n+1][3]
f[i][k] = min{f[j][k-1]+sumD[i](sumW[i-1]-sumW[j]) - (sumDW[i-1]-sumDW[j])}

移项
f[j][k-1]+sumDW[j] = sumD[i]sumW[j] + f[i][k] + sumDW[i-1] - sumD[i]sumW[i-1]
(sumW[j], f[i][k-1]+sumDW[j])
1. 横坐标单调递增
2. 斜率单调递增
时间复杂度 O(Nlog(N)) = 610^520 = 1e7;

时间复杂度

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=200005;
LL n, d[N], sumD[N], w[N], sumW[N], sumDW[N], q[N];
LL f[N][5];
double long check(int i, int j, int k){
    return (f[i][k]+sumDW[i]-f[j][k]-sumDW[j])*1.0/(sumW[i]-sumW[j]);
}
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>w[i]>>d[i];
        sumD[i+1] = sumD[i]+d[i]; 
        sumW[i] = sumW[i-1]+w[i];
        sumDW[i] = sumDW[i-1]+sumD[i]*w[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for(int k=1; k<=3; k++){
        int hh=0, tt=0;
        for(int i=1; i<=n+1; i++){
            // for(int j=0; j<i; j++){
            //     f[i][k] = min(f[i][k], f[j][k-1]+sumD[i]*(sumW[i-1]-sumW[j]) - (sumDW[i-1]-sumDW[j]));
            // }
            while(hh<tt && check(q[hh+1], q[hh], k-1)<sumD[i]) hh++;
            int j = q[hh];
            f[i][k] = f[j][k-1]+sumD[i]*(sumW[i-1]-sumW[j]) - (sumDW[i-1]-sumDW[j]);
            while(hh<tt && check(q[tt], q[tt-1], k-1)>=check(i, q[tt-1], k-1)) tt--;
            q[++tt] = i;
        }
    }
    cout<<f[n+1][3];
}