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

d[i]表示i号小猫到1号山的距离
首先对于每一只猫i，要想能够接上它， 那么其从si开始的时间， si>=d[i]+t[i]

s[i] 表示排序好的小猫的前缀和, ss[i] 表示 s[i] 的前缀和
f[i] 接受到表示前i只小猫花费的时间（显然刚好卡在第i只猫的等待时间去接）
f[i] = min(f[j] + (i-j-1)s[i] - (ss[i-1]-ss[j]))
f[j] + ss[j] = s[i]j + f[i]- i*s[i] + s[i] + ss[i-1]

求这一部分的最小值， 截距要小 f[i]- i*s[i] + s[i] + ss[i-1]
(j, f[j]+ss[j]) 斜率s[i]
1. 横坐标单调递增
2. 斜率单调递增

时间复杂度

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100005;

LL d[N], a[N], s[N], ss[N], q[N], f[N][105];
int n, m, p;
double long check(int i, int j, int k){
    return (f[i][k]+ss[i]-f[j][k]-ss[j])*1.0/(i-j);
}
int main(){
    cin>>n>>m>>p;
    for(int i=2; i<=n; i++){
        cin>>d[i];
        d[i] += d[i-1]; //d[i] 表示 第i个点到1号上的距离；
    }
    for(int i=1, h, t; i<=m; i++){
        cin>>h>>t;
        s[i] = t-d[h];//这里注意一点
    }
    sort(s+1, s+m+1); //将小猫的时间从小到大排序
    for(int i=1; i<=m; i++){
        ss[i] = ss[i-1]+s[i];
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for(int k=1; k<=p; k++){
        int hh=0, tt=0;
        for(int i=1; i<=m; i++){
            while(hh<tt && check(q[hh+1],q[hh],k-1)<s[i]) hh++;
            int j=q[hh];
            f[i][k] = f[j][k-1] + (i-j-1)*s[i] - (ss[i-1]-ss[j]);
            while(hh<tt && check(q[tt], q[tt-1], k-1)>=check(i, q[tt-1], k-1)) tt--;
            q[++tt]=i;
            // for(int j=0; j<i; j++){
            //     f[i][k] = min(f[i][k], f[j][k-1] + (i-j-1)*s[i] - (ss[i-1]-ss[j]));
            // }
        }
    }
    cout<<f[m][p]<<endl;
    return 0;
}