题目
有 M M M只猫，雇了 P P P位饲养员。路边有 N N N座山，从 1 1 1到 N N N编号。第 i i i座山与第 i − 1 i−1 i−1座山之间的距离是 D i D_i Di 。饲养员都住在 1 1 1号山上。第 i i i只猫去 H i H_i Hi号山玩，玩到时刻 T i T_i Ti停止，然后在原地等饲养员来接。饲养员们必须回收所有的猫。每个饲养员沿着路从 1 1 1号山走到 N N N号山，把各座山上已经在等待的猫全部接走。饲养员在路上行走需要时间，速度为 1 1 1米每单位时间。饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。
你的任务是规划每个饲养员从 1 1 1号山出发的时间，使得所有猫等待时间的总和尽量小。饲养员出发的时间可以为负。
分析
设 A i = T i − ∑ j = 1 d i A_i=T_i-\sum_{j=1}^{d_i} Ai=Ti−∑j=1di
这道题朴素的动态规划， f [ i ] [ j ] = m i n { f [ i − 1 ] [ k ] + A [ i ] ∗ ( j − k ) − ( ∑ p = k + 1 j a [ p ] ) } f[i][j]=min\{f[i-1][k]+A[i]*(j-k)-(\sum_{p=k+1}^ja[p])\} f[i][j]=min{f[i−1][k]+A[i]∗(j−k)−(∑p=k+1ja[p])}
所以可以发现这是一个斜率优化，发现这个，还可以发现求的是下凸壳
代码
#include <cstdio>
#include <algorithm>
typedef long long ll; ll f[2][100001],a[100001];
int n,m,p,d[100001],q[100001];
ll in(){
ll ans=0; int f=1; char c=getchar();
while ((c<48||c>57)&&c!='-') c=getchar();
if (c=='-') c=getchar(),f=-f;
while (c>47&&c<58) ans=ans*10+c-48,c=getchar();
return ans*f;
}
int main(){
n=in(); m=in(); p=in(); ll ans=1ll<<62;
for (register int i=2;i<=n;i++) d[i]=d[i-1]+in();
for (register int i=1,x;i<=m;i++) x=in(),a[i]=in()-d[x];
std::stable_sort(a+1,a+1+m); bool x=0;
for (register int i=2;i<=m;i++) a[i]+=a[i-1];
std::fill(f[x]+1,f[x]+1+m,1ll<<62);
for (register int i=1;i<=p;i++){
int l=1,r=1; q[1]=0; x^=1;
for (int j=1;j<=m;j++){
while (l<r&&f[x^1][q[l+1]]+a[q[l+1]]-a[q[l]]-f[x^1][q[l]]<(a[j]-a[j-1])*(q[l+1]-q[l])) l++;//队头没有用的需要出队
f[x][j]=f[x^1][q[l]]+(a[j]-a[j-1])*(j-q[l])-(a[j]-a[q[l]]);//动态规划，当然用了滚动数组
while (l<r&&(f[x^1][q[r]]+a[q[r]]-f[x^1][q[r-1]]-a[q[r-1]])*(j-q[r])>(f[x^1][j]+a[j]-a[q[r]]-f[x^1][q[r]])*(q[r]-q[r-1])) r--;//队尾不优的出队
q[++r]=j;//入队
}
ans=std::min(ans,f[x][m]);
}
return !printf("%lld",ans);
}