题解：P11602 『Fwb』黑巧の安排

LostKeyToReach · 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 很大时，你有什么更优秀的解法吗？