本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-19 15:58:41

题解思路：

转化题意：

我们先求一下从第一座山到以后的每一座山的距离先求出来，也就是对 $d_i$ 求一个前缀和。

那么现在的 $d_i$ 就表示 $1$~$i$ 的距离。

一个饲养员走到一个猫的山开始的时间为 $s_i$。

那么若 $s_i + d_i \ge ti$ 那么饲养员才能把第 $i$ 只小猫接上。

那么这只小猫的等待时间为： $$s_i+\Delta t - (t_i-d_i)$$

那么我们用 $a_i$ 来表示 $t_i-a_i$。

那么 $a_i$ 就是要接走这只猫的最早出发时间。

那么我们把小猫的 $a_i$ 从小到大排序。

那么饲养员出发的时候，每一次饲养员每次都要接走一批的小猫。

若一个饲养员要接走前 $i$ 只小猫，那么就要在 $a_i$ 时刻出发，当然这里的 $a_i$ 是排序后的值。

那么前 $i$ 等待的时间之和就是： $$a_i-a_i+a_i-a_{i-1}+...+a_i-a_l$$ $$=a_i*(i-l+1)-(Sum_i-Sum_{l-1})$$ 其中 $l$ 表示这段区间的左端点，$i$ 就是右端点，$Sum$ 就是 $a_i$ 的前缀和。

那么就相当于有 $m$ 个数，然后我们给他分成 $p$ 组，然后每组的最后一个减去其他的差的和的最小值。

这样的话就转化成了和这道题类似了。

然后我们用斜率优化DP来做就可以了。

解法：

那么我们设 $f_{j,i}$ 表示：前 $i$ 只小猫分成 $j$ 组的最小等待时间也就是用 $j$ 个饲养员。

状态转移方程： $$f_{j,i} = \max\{f_{j-1,k} + a_i \times (i-k) - (Sum_i-Sum_k)\}$$

我们把 $i$ 和 $j$ 看作常量，那么变形： $$f_{j,i} = f_{j - 1 , k} - a_i \times k + Sum_k + a_i \times - Sum_i$$

那么和 $k$ 有关的变量有： $$f_{j-1,k},k,Sum_k$$

整理一下： $$f_{j-1,k} + Sum_k = a_i \times k + f_{j,i} - a_i\times i + Sum_i$$

因为我们对 $a_i$ 排序了，所以 $a_i$ 是单调递增的。

那么 $f_{j,i} - a_i \times i + Sum_i$ 就是截距。

那么 $k$ 就是 $x$，$f_{j-1,k} + Sum_k$ 是 $y$。

时间复杂度为 $\mathcal{O}(pm)$。

十年OI一场空，不开long long见祖宗！

AC CODE

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010 , M = 100010 , P = 110;
int n , m , p;
ll d[N] , t[N] , a[N] , s[N];
ll f[P][M];
int q[M];
ll get_y(int k , int j) {
	return f[j - 1][k] + s[k];
}
int main(){
    scanf ("%d%d%d" , &n , &m , &p);
	for (int i = 2; i <= n; ++ i){
	    scanf ("%lld" , &d[i]);
		d[i] += d[i - 1];\/\/预处理前缀和。
	}
	for (int i = 1; i <= m; ++ i){
		int h;
		scanf ("%d%lld" , &h , &t[i]);
		a[i] = t[i] - d[h];\/\/a数组
	}
	sort (a + 1 , a + 1 + m);\/\/排序
	for (int i = 1; i <= m; ++ i) s[i] += s[i - 1] + a[i];\/\/a的前缀和
	memset (f , 0x3f , sizeof (f));
	for (int i = 0; i <= p; ++ i) f[i][0] = 0;
	for (int j = 1; j <= p; ++ j) {\/\/DP
		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;
			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;
		}
	}
	printf ("%lld\n" , f[p][m]);
	return 0;
}