二刷提高课，题解目录在这里— 提高课的题解目录

对于每一只小猫，如果小猫刚玩完饲养员就来了即st+sumd=t，此时小猫没有等待
既然对于每一只小猫都有这个特性，来早了接不到，来晚了要等时间
那我们就将这个特性收集起来，然后进行排序，可以发现这些就是在数轴上的一系列点
并且当某个饲养员决定从某个点走的时候，那么他肯定不会这个点之前在跳着取猫
假设 1 2 3 4四个点，饲养员在4走的，这些猫他都可以取走，但是为了使得等待时间最短
为了让3少等一些选择了跳着走，选择了 2 4，很明显这并不是最优的
因为我们可以让2被取3的饲养员取走，那样时间会更少，所以说，饲养员一定是选择连续的一些点（可以为1）
那不就转换成了上一题的批处理作业了吗
但是，这里饲养员有数目限制！
所以我们的状态转移中必须含有饲养员所使用的数目
这里用f[j][i]来表示，y总说这样会快点，原因是操作系统处理连续地址会快点
接下来就是如何进行状态转移了
很明显应该找上一步分批的边界点，这里为k所以就是找k使得结果最小
然后再用上斜率优化（与上题类似）

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+10,P=110;
ll d[N],t[N],a[N],s[N];
ll f[P][N];
int q[N];
int n,m,p;
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 x;
        cin>>x>>t[i];
        a[i]=t[i]-d[x];
    }
    sort(a+1,a+1+m);
    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;
        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 ++ ;
            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];
    return 0;
}