10187. 「一本通 5.6 例 4」Cats Transport

题意

小S养了$M$只猫,雇了$P$位饲养员。农场旁边有$N$座山,从$1$到$N$编号,第$i$座山与第$i-1$座山的距离为$D_i$,饲养员都住在$1$号山上。 有一天,第$i$只猫到第$H_i$座山玩,一直玩到$T_i$停止。饲养员们必须接回所有的猫,饲养员们行走的速度为$1$个单位每单位时间。 问如何计划每个饲养员从$1$号山出发的时间,使得所有猫的等待时间最少。

思路

设$A_i=T_i-\sum{D_j}(1 \leq j \leq H_i)$。一名饲养员若想接到第$i$只猫就必须要在$A_i$时刻出发。若出发时间为$t$,那么这只猫等待的时间就是$t-A_i$。 先把$A_i$从小到大排序,求出排好序的$A$数组的前缀和,记录在数组$S$中。 然后根据贪心的思想,每个饲养员带走的猫一定是按照$A$从小到大排序后的连续的几只猫。 设$f[i][j]$表示前$i$个饲养员带走前$j$只猫,猫们等待的最少时间。 很容易就可以得出转移方程: $$f[i][j]=min(f[i-1][k]+a[j]\times (j-k) – (s[j]-s[k]))(0 \leq k < j)$$ 直接枚举$k$肯定会超时,时间复杂度为$O(PM^2)$。 将$min$去掉,进行化简、移项可得: $$f[i-1][k]+s[k]=a[j] \times k +f[i][j]-a[j]\times j +s[j]$$ 设$y=f[i-1][k]+s[k],k=a[j],x=k,b=f[i][j]-a[j] \times j+s[j]$。由一次函数$y=kx+b$可得,当$b$为最小时,$f[i][j]$取得最小值。 那么就加上单调队列斜率优化即可。
暂无评论

发送评论


				
上一篇
下一篇