盒子堆叠问题的o（n ^ 2）解决方案是否有更快？

Question

堆栈堆叠问题如下：

给出了一组 $ n $ 类型的矩形3-d盒，其中 $ i ^ {th} $ 框有高度 $ h_i $ ，width $ w_i $ 和深度 $ d_i $ （全部真实 数字）。您想创建一堆框，这与 可能的，但如果如果是，你只能在另一箱顶部堆叠一个盒子 下箱的2-D底座的尺寸每个都严格较大 比较高框的2亿底部的那些。当然可以 旋转一个盒子，使任何侧面用作其基础。也是 允许使用相同类型的框的多个实例。

是否有一个速度比 $ o（n ^ 2）$ 解决方案给出这里？

Answer 1

这可以通过使用2D范围查询数据结构来优化的。在问题上给出的链接中解释的动态编程解决方案：

如在链接中，对于输入尺寸的框 $（w_i，d_i，h_i）$ ，考虑框的所有旋转，但保持第一个维度始终 $ \ ge $ 第二维度。因此，每个输入框对应于三个框，并考虑所有这些 $ 3n $ 框，并在基础的减少区域中对它们进行排序（即前两个产品尺寸）。

让这种排序序列是 $（a_1，b_1，c_1），（a_2，b_2，c_2），\ ldots，（a_ {3n}，b_ {3n}，c_ {3n}）$ 。

让 $ dp [i] $ 是您可以使用第一个 $ i $ 框在此序列中，使最顶层框是 $ i ^ {th} $ box。最初 $ dp [i]= 0 $ 对于所有 $ i $ 。复发是

$ dp [i]= c_i + \ max _ {\ subsamp {j a_i \\ b_j> b_i}} dp [j] $

现在，而不是消费 $ \ mathcal {o}（n）$ 时间来查找此最佳 $ j $ ，我们将使用某些数据结构更快地进行。想想每个框 $（a_j，b_j，c_j）$ 作为一个点 $（a_j，b_j）$ 在2D平面中，具有值 $ dp [j] $ 。现在我们想要找到的是矩形 $ [a_i + 1，inf] \ times [b_i + 1，inf] $ ，它具有最大值。请注意，我们可以忽略约束 $ j ，因为它将被隐式满足维度约束。

为此，构造一个 2d段树aka fenwick树（查看2d段树的压缩'压缩'），使用 $ a_i $ 作为外部段树中的值， $ b_i $ 作为内部段树中的值。您还可以使用大多数其他2D范围查询数据结构。

您可以查询 $ \ mathcal {o}（\ log ^ 2 {} n）$ 时间，并且一旦您拥有computed $ dp [i] $ ，您必须在所有 $ \ mathcal {o}中更新该值中的该值（\ log {} n）$ 内部段树，总共需要 $ \ mathcal {o}（\ log ^ 2 {} n）$ 时间。

因此，问题可以在 $ \ mathcal {o}中解决问题（n \ log ^ 2 {} n）$ time，以及 $ \ mathcal {o}（n \ log {} n）$ 空格。