CF1801F Another n-dimensional chocolate bar 题解
考虑到最多只会有一个 $b_i \ge \sqrt{k}$。
- 没有任何一个 $b_i \geq \sqrt{k}$。
那么我们可以考虑类似 meet-in-the-middle 的做法。
令 $f_{i,j}$ 表示考虑了前 $i$ 个数，此时乘积为 $j$，$\lfloor\frac{a_1}{b_1}\rfloor\lfloor\frac{a_2}{b_2}\rfloor\dots\lfloor\frac{a_i}{b_i}\rfloor\frac{1}{a_1a_2\dots a_i}$ 的最大值，$g_{i,j}$ 的定义类似，不过是从 $n$ 开始倒着的。dp 的时候枚举 $i$，枚举 $j$，再枚举满足 $j\times k \le$ 第二维大小的所有 $k$ 即可。
则我们这种情况下的最好答案就是枚举一个中间断点 $i$，和 $i$ 左边的部分的乘积 $j$，$f_{i,j}\times g_{i+1,\lceil\frac{k}{j}\rceil}$ 的最小值了。
此时我们需要证明，在所有选择的 $b_i$ 都 $\le \sqrt{k}$ 的情况下，$f$ 和 $g$ 的第二维都只要开到 $k^{\frac{3}{4}}$ 即可。
不妨设一个 $x$，初始为 $b_i$ 最大的位置，令 $p$ 为 $x$ 左边所有 $b_i$ 的乘积，$q$ 为 $x$ 右边所有 $b_i$ 的乘积。
我们贪心的考虑，如果 $b_x^2\times p <q$，就让 $x+1$；如果 $b_x^2\times q < p$，就让 $x-1$。在移动 $x$ 的同时维护 $p$ 和 $q$ 的值。
此时第二维就需要开到一个 $\min(p,q)\times b_x$ 的大小。因为 $p \times q \times b_x$ 是 $O(k)$ 级别的，所以 $\min(p,q)\le \sqrt{\frac{k}{b_x}}$，故第二维只需要开到 $\sqrt{\frac{k}{b_x}}\times b_x=\sqrt{k\times b_x}$ 即可。因为 $b_x\le \sqrt{k}$，所以 $\sqrt{\frac{k}{b_x}}\times b_x \le k^{\frac{3}{4}}$，得证。
综上，该部分复杂度为 $O(n\times k^{\frac{3}{4}}\times\log(k^{\frac{3}{4}}))$。
- 存在恰好一个 $b_i \geq \sqrt{k}$。
那么我们可以直接枚举这个 $i$，发现 $i$ 左侧和右侧 $b_j$ 的乘积均 $\le \sqrt{k}$。令 $h_j$ 表示现暂时不选 $b_i$，其他所有位置都选之后乘积为 $j$ 时的最大值。这个可以利用 $f_{i-1}$ 和 $g_{i+1}$ 快速处理。
然后我们枚举除了 $b_i$ 的所有 $b_j$ 的乘积 $t$，推出 $b_i$ 的值最小是多少，计算出 $\lfloor\frac{a_i}{b_i}\rfloor\frac{1}{a_i}$ 即第 $i$ 个数的贡献，乘上 $h_t$ 即可。
该部分复杂度为 $O(n\sqrt{k})$。
综上，总复杂度为 $O(n\times k^{\frac{3}{4}}\times\log(k^{\frac{3}{4}}))$，可以不知道为什么但只跑了1.5s通过此题。
1 |
|