$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

$a_i=t_i-d_i，饲养员最早也要从\ a_i\ 时刻出发才能接走小猫，s_i\ 是\ a_i\ 排序后的前缀和$

$f[j][i]\ 表示\ j\ 个饲养员接走前\ i\ 只小猫的猫咪最少等待时间，饲养员每次接走\ [k+1,i]\ 的一批小猫$

$\begin{aligned}因为\ f[j][i] & = f[j-1][k]+a[i]\cdot (i-k)-(s[i]-s[k]) \\\\ & = f[j-1][k]-a[i]\cdot k+s[k]+a[i]\cdot i-s[i]\end{aligned}$

$所以\ f[j-1][k]+s[k]=a[i]\cdot k+f[j][i]-a[i]\cdot i+s[i]$

$那么，y=f[j-1][k]+s[k]，x=k，斜率=a[i]，b=f[j][i]-a[i]\cdot i+s[i]$

$查询：删去小于等于\ a[i]\ 的斜率，那么队头\ f[j-1][q[hh]]\ 即可使\ f[j][i]\ 最小$

$插入：若队尾和队尾前一个点之间的斜率大于等于插入点和队尾之间的斜率，那么就将队尾删去$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010, M = 110;

int n,m,p;
int q[N];
LL t[N],d[N],a[N],s[N];
LL f[M][N];

LL get_y(int k,int j)
{
    return f[j-1][k]+s[k];
}

int main()
{
    cin>>n>>m>>p;

    for(int i=2;i<=n;i++)
    {
        cin>>d[i];
        d[i]+=d[i-1];
    }

    for(int i=1;i<=m;i++)
    {
        int h;
        cin>>h>>t[i];
        a[i]=t[i]-d[h];
    }

    sort(a+1,a+m+1);

    for(int i=1;i<=m;i++) s[i]=s[i-1]+a[i];

    memset(f,0x3f,sizeof f);
    for(int i=0;i<=p;i++) f[i][0]=0;

    for(int j=1;j<=p;j++)
    {
        int hh=0,tt=0;
        q[0]=0;
        for(int i=1;i<=m;i++)
        {
            while(hh<tt&&(get_y(q[hh+1],j)-get_y(q[hh],j))<=a[i]*(q[hh+1]-q[hh])) hh++; //找到第一个大于 a[i] 的斜率
            int k=q[hh];
            f[j][i]=f[j-1][k]-a[i]*k+s[k]+a[i]*i-s[i];
            while(hh<tt&&(get_y(q[tt],j)-get_y(q[tt-1],j))*(i-q[tt])>=(get_y(i,j)-get_y(q[tt],j))*(q[tt]-q[tt-1])) tt--;
            q[++tt]=i;
        }
    }

    cout<<f[p][m]<<endl;

    return 0;
}