标签：小猫 min 题解 sum times Cats CF311B frac dp

思路

首先，对于每一只小猫刚好玩完就被饲养员接走的出发时间必定为 \(t_i - sd_i\)。

那么，我们令 \(a_i = t_i - sd_i\)表示第 \(i\) 只小猫的最早出发时间。

因此，对于第 \(k\) 时刻出发的饲养员能接到的小猫当且仅当满足 \(a_i \leq k\)。

然后，我们定义 \(dp_{i,j}\) 表示用 \(i\) 个饲养员，接走 \(j\) 只小猫的最小代价。

得状态转移方程：

\[ dp_{i,j} = \min(dp_{i - 1,k} + \sum_{u = k + 1}^j(a_j - a_u)) \]

化简得：

\[ dp_{i,j} = \min(dp_{i - 1,k} + \sum_{u = k + 1}^ja_j - \sum_{u = k + 1}^ja_u) \]

用前缀和优化得：

\[ dp_{i,j} = \min(dp_{i - 1,k} - a_j \times k + a_j \times j + s_j - s_k) \]

如果选 \(k_2\) 优于 \(k_1\)，当且仅当满足如下条件：

\[ dp_{i - 1,k_1} - a_j \times k_1 + a_j \times j + s_j - s_{k_1} > dp_{i - 1,k_2} - a_j \times k_2 + a_j \times j + s_j - s_{k_2} \]

化简，有：

\[ dp_{i - 1,k_1} - a_j \times k_1 - s_{k_1} > dp_{i - 1,k_2} - a_j \times k_2 - s_{k_2} \]

\[ \frac{(dp_{i - 1,k_1} - s_{k_1}) - (dp_{i - 1,k_2} - s_{k_2})}{k_1 - k_2} > a_j \]

\[ \frac{(dp_{i - 1,k_2} - s_{k_2}) - (dp_{i - 1,k_1} - s_{k_1})}{k_2 - k_1} > a_j \]

不妨令：

1. \(dp_{i - 1,x} - s_x\) 为 \(Y(x)\)。
2. \(k_x\) 为 \(X(i)\)。
3. \(a_j\) 为 \(K\)。

那么，有：

\[ \frac{Y(k_2) - Y(k_1)}{X(k_2) - X(k_1)} < K \]

标签：小猫,min,题解,sum,times,Cats,CF311B,frac,dp
From： https://www.cnblogs.com/WaterSun/p/18263299