自动搬运

查看原文

来自洛谷，原作者为

	Yonder Morose Dreamer

搬运于2025-08-24 22:02:28，当前版本为作者最后更新于2025-06-08 11:49:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神秘题。

看到 $p,v\le1000$ 考虑将 dp 的状态与时间相关联。

令 $dp_i$ 表示时间为 $i$ 时的最多成员数。

则 $dp_i=\displaystyle\max_{1\le j\le\frac{i-v}{p}}\{dp_{i-v-j\times p}\times j\}$。

那么当 $dp_i\ge n$ 时，$i$ 即为答案。

考虑分析复杂度。

后面那个 $\times j$ 是个很好的切入点，相当于我只需要花费 $v+j\times p$ 的代价就可以让答案乘 $j$。但是这个 dp 是二重循环，所以我们考虑判断一个固定的 $j$ 满足答案需要的复杂度，即 $O(\frac{[(v+j\times p)\times\log_jn]^2}{p})$。最坏大概是 $O(p(e+1)\ln^2n)$。