给定一个有 4 行和 4 列的棋盘n。每个单元格上都有一个整数。给定2n其中一部分或全部的光盘，您可以将它们放在板上的不同单元格上，以便总和最大。唯一的限制是 2 个圆盘不能垂直或水平相邻。O(n)使用 DP时如何在棋盘上放置最佳组合？
问问题
184 次
1 回答
1
第一，我们不可能使用超过 2*n 个磁盘，因为任何列最多可以包含 2 个磁盘。
假设 d[i][mask] - 用磁盘填充从 1 到 i 的列后获得的最大数量，以便最后一列填充为掩码（掩码可以是 0000、0001、0010、0100、0101、1000、1001 或 1010其中 1 表示已放置磁盘，0 表示未放置）
所以 d[i][mask1] = max of (d[i-1][mask2] + 通过在第 i 列上应用 mask1 获得的数字)，其中 mask2 可以是与 mask1 不矛盾的任何掩码
编辑 1：您不需要更改任何内容。当你在某个面具上的第 i 步时，它只取决于 i-1 面具的答案。你已经拥有了所有这些。您只需尝试从有效的 d[i][mask] 中更新当前的 d[i][mask]。正如我已经说过的 d[i][mask] - 存储从 1 到 i 填充列可以获得的最大值，最佳地，以便最后一列具有此掩码形式的磁盘（在 i 之前的掩码无关紧要-th 列已填满，因为它们不会影响下一列）
于 2015-05-20T04:19:20.590 回答