题意:小S是一个大农场主.他养了m只可爱的猫,雇佣了p个饲养员.农场中有一条笔直的路，路边有N座山，从1到N编号.山丘i与山丘i-1的距离是(d_i)米.饲养员都住在1号山丘.一天，猫外出玩耍.猫i去山丘(h_i)游玩，在(t_i)时间结束他的游玩，然后在原地傻等饲养员.饲养员必须把所有的猫带回.每个饲养员直接从1号山走到N号山，不花费时间的把已经游玩结束的猫带回.每个铲屎官的速度为一米每单位时间，并且足够强壮来带上任意数量的猫.举个栗子，假装我们有两个相距为1的山丘,有一只猫，他想去山丘2玩到时间3.然后饲养员如果在时间2或者时间3从1号山丘出发，他就能抱走猫.如果他在时间1出发那么就不行(猫子还在玩耍).如果饲养员在时间2出发，猫就不用等他（ΔT=0）.如果他在时间3出发，猫就要等他1个单位时间。你的任务是安排每个饲养员出发的时间，最小化所有猫等待的时间之和.
分析:对于每只猫,设(A[i]=t[i]-sum_{j=1}^{h[i]}d[j]),一名饲养员如果想接到第i只猫,就必须要在(A[i])时刻之后从1号山出发.若出发时刻为t,则猫的等待时间就是(t-A[i])
预处理出A数组,并从小到大排序,这样一个饲养员接走的猫一定是连续的一群,这样本题就是斜率优化的模板题了.
设(f[i][j])表示前i个饲养员接走前j只猫的最小等待时间,则有,
(f[i][j]=f[i-1][k]+A[j]*(j-k)-(S[j]-S[k]))其中S数组是A数组排好序后的前缀和数组
设l<k且k比l更优,即
(f[i-1][k]+A[j]*(j-k)-(S[j]-S[k])<f[i-1][l]+A[j]*(j-l)-(S[j]-S[l]))
整理一下上式得到,
(frac{f[i-1][k]+S[k]-f[i-1][l]-S[l]}{k-l}<A[j])
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
const int N=200005;
const int M=100005;
int d[N],h[M],t[M],q[N];
LL D[N],sum[M],a[M],f[105][M];
int main(){
int n=read(),m=read(),p=read();
for(int i=2;i<=n;i++){
d[i]=read();
D[i]=D[i-1]+d[i];
}
for(int i=1;i<=m;i++){
h[i]=read();t[i]=read();
a[i]=t[i]-D[h[i]];
}
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)sum[i]=sum[i-1]+a[i];
memset(f,0x3f,sizeof(f));
for(int i=0;i<=p;i++)f[i][0]=0;
for(int i=1;i<=p;i++){
int l=1,r=1;q[1]=0;
for(int j=0;j<=m;j++){
while(l<r&&(f[i-1][q[l+1]]+sum[q[l+1]])-(f[i-1][q[l]]+sum[q[l]])<=(q[l+1]-q[l])*a[j])l++;
f[i][j]=f[i-1][q[l]]+sum[q[l]]+a[j]*j-sum[j]-a[j]*q[l];
while(l<r&&((f[i-1][q[r]]+sum[q[r]])-(f[i-1][q[r-1]]+sum[q[r-1]]))*(j-q[r])>=((f[i-1][j]+sum[j])-(f[i-1][q[r]]+sum[q[r]]))*(q[r]-q[r-1]))r--;
q[++r]=j;
}
}
printf("%lld
",f[p][m]);
return 0;
}