自动搬运

查看原文

来自洛谷，原作者为

	LostKeyToReach 争取今年不退役 || int_stl. || 有意互关私。

搬运于2025-08-24 23:08:46，当前版本为作者最后更新于2025-01-21 16:48:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

有一个很显然的 dp 做法。

令 $dp_i$ 表示恰好吃 $i$ 天的最小巧克力数量，那么有转移：

其中 $2^j - 1 = \displaystyle \sum_{k = 1} ^ j 2^{k - 1}$。

请注意，我们这里令 $i - j + 1$ 重新开始按规律吃巧克力，故在 $dp_{i - j} < 2^j$ 时才可以转移。

那么 $j$ 的范围是什么呢？首先，肯定有 $1 \le j \le i$。其次，由于答案不超过 $64$ 位有符号整数的范围，故 $j \le 60$。综上，我们只需在 $[1, \min(i, 60)]$ 的范围内枚举 $j$ 即可。

处理完 dp 就可以 $O(1)$ 回答了。

这里的时间复杂度为 $O(t + 60V)$，足以通过本题了。

Challenge：当 $V$ 很大时，你有什么更优秀的解法吗？