题解

思路

把已经获得的块数超过 $k$ 的状态统一截断为 $k$。若当前还需要把块数再扩大到原来的 $r$ 倍，沿新维度切成 $c$ 份后，新的需求为 $\lceil r/c\rceil$，体积倍率为 $\lfloor a_i/c\rfloor/a_i$。

子任务 1

枚举每一维的 $b_i=1,2,\ldots,a_i$，在叶子检查乘积是否至少为 $k$，直接计算目标值。复杂度为 $O(\prod a_i)$。

子任务 2

令 dp[j] 表示处理若干维后恰好得到 min(实际块数,k)=j 时的最大目标值前缀。对每个有效 $j$ 枚举切分数 $c$，当 $jc<k$ 时正常转移；达到 $k$ 后只需考虑最小的 $c=\lceil k/j\rceil$。利用调和级数，单维转移为 $O(k\log k)$。

子任务 3

改用“剩余倍率”状态。所有 $\lceil k/i\rceil$ 只有 $O(\sqrt k)$ 个不同值。对于一个剩余倍率 $r$，其转移目标 $\lceil r/c\rceil$ 同样只有 $O(\sqrt r)$ 个不同值；对每段只保留最小 $c$，因为它让 $\lfloor a_i/c\rfloor$ 最大。

依次生成商相同区间的左端点：当前值为 $q=\lceil r/c\rceil$ 时，下一个左端点为 $\lceil r/(q-1)\rceil$。预处理所有压缩状态及转移后进行滚动 DP。

做法

1. 枚举并编号全部不同的 $\lceil k/i\rceil$。
2. 对每个压缩状态生成所有不同目标状态及对应的最小切分数 $c$。
3. 初始剩余倍率为 $k$，初始数值为 $k$。
4. 逐维乘上 $\lfloor a_i/c\rfloor/a_i$ 并取最大值，最终读取剩余倍率为 $1$ 的状态。

正确性证明

状态 $r$ 精确表示当前仍需把块数扩大至少 $r$ 倍；选择 $c$ 后新需求为 $\lceil r/c\rceil$，因此转移无误。对产生同一新需求的多个 $c$，较小的 $c$ 具有不小的 $\lfloor a_i/c\rfloor$，所以只保留区间左端点不丢失最优解。DP 枚举每一维的全部不同有效决策，最终 $r=1$ 恰表示总块数至少为 $k$，故答案正确。

复杂度

满分算法时间复杂度为 $O(nk^{3/4})$，空间复杂度为 $O(\sqrt k+nk^{3/4})$ 的预处理转移与滚动状态；实现中 DP 本身为 $O(\sqrt k)$ 空间。中档为 $O(nk\log k)$，小档为指数复杂度。