Cats Transport

小S是农场主，他养了M只猫，雇了P位饲养员。农场中有一条笔直的路，路边有N座山，从1到N编号。第i座山与第i-1座山之间的距离是 $D_i$ 。饲养员都住在1号山上。
有一天，猫出去玩。第i只猫去 $H_i$ 号山玩，玩到时刻 $T_i$ 停止，然后在原地等饲养员来接。饲养员们必须回收所有的猫。每个饲养员沿着路从1号山走到N号山，把各座山上已经在等待的猫全部接走。饲养员在路上行走需要时间，速度为1米每单位时间。饲养员在每座山上接猫的时间可以忽略，可以携带的猫的数量为无穷大。
例如有两座相距为1的山，一只猫在2号山玩，玩到时刻3开始等待。如果饲养员从1号山在时刻2或3出发，那么他可以接到猫，猫的等待时间为0或1。而如果他于时刻1出发，那么他将于时刻2经过2号山，不能接到当时仍在玩的猫。
你的任务是规划每个饲养员从1号山出发的时间，使得所有猫等待时间的总和尽量小。饲养员出发的时间可以为负。

#include<bits/stdc++.h> using namespace std; const int nm=101020; int n,m,p,h,t,tt,q[nm]; long long d[nm],a[nm],s[nm],f[2][nm]; double slo(int i,int j){return 1.0*(f[0][j]+s[j]-f[0][i]-s[i])/(j-i);} 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++) scanf("%d%d",&h,&t), a[i]=1ll*t-d[h]; sort(a+1,a+m+1); for(int i=1;i<=m;i++) f[0][i]=a[i]*i-(s[i]=s[i-1]+a[i]); for(int i=2;i<=p;i++){ for(int j=1,k;j<=m;j++){ if(t>=tt)t=tt; else while(t<tt&&slo(q[t],q[t+1])<a[j])t++; k=q[t],f[1][j]=f[0][k]+a[j]*(j-k)-(s[j]-s[k]); while(tt&&slo(q[tt-1],q[tt])>=slo(q[tt],j))tt--; q[++tt]=j; }memcpy(f[0],f[1],sizeof f[0]),t=tt=0; }return printf("%lld\n",f[0][m]),0; }

详情