c - 动态规划图块

Question

http://www.spoj.pl/problems/GNY07H/ 在这个问题中，我们必须找到在 4Xw (w >=1) 矩形中排列 2X1 瓷砖的多种方法？我已经尝试过这个问题并且花了很多时间，但无法提出任何解决方案。如何解决这类问题。意思是如何让 dp 为他们重复。?

score 11 · Accepted Answer

您可以逐行构建 4xW 矩形。当您构建下一行时，前一行可以处于 6 种不同的状态：

XXXX (1 - filled)
XX-- (2)
-XX- (3)
--XX (4)
X--X (5)
---- (6 - empty)

例如，如果上一行是 (5)，则必须放置两个垂直的多米诺骨牌，然后下一行将是 (3)：

XXXX
XABX
-AB-

让X(W,q)表示一个 4xW 矩形的可能组合，其中最后一行处于状态q，其余行完全填充。

如果您知道X(W-1,q)所有 6q个州，您可以轻松计算X(W,q).

你知道初始状态X(1,q)（q=1..6 -> 1, 1, 1, 1, 1, 无效）。所以你可以增加 W 并为每个 W 获得这些数字。

最终结果是X(W,1)（填充最后一行）。

score 8 · Accepted Answer

我也是这种动态编程变体的初学者，但此链接提到您需要申请“带有配置文件的动态编程”，并且该链接还指向一个教程http://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0&mc=19特别是“层数+层配置文件”。

从上面的链接：“这是DP状态域中最难的类型。它通常用于在特殊图上平铺或覆盖问题。经典的例子是：计算用多米诺骨牌平铺矩形板的方法数（某些单元格不能“

有关此技术的其他更平易近人的教程可在以下位置获得：

我也在努力解决它们。

这不是对您提出的特定问题的答案，而是人们在解决此类问题时遵循的一般技术。

score 0 · Accepted Answer

我会尝试回溯算法：首先水平放置所有瓷砖，然后回溯，直到可以放置垂直瓷砖（然后水平分层向前） - 最终您将枚举所有可能的解决方案并且每个解决方案仅一次（最后一个回溯阶段中的正方形将包含水平或垂直瓷砖，如果存在，它将提供独特的解决方案）。

但是，我不知道这是否是解决问题的最佳算法。

score 0 · Accepted Answer

如果通过删除任何 2*1 块出现模式（gemoetry ）使其再次成为中间结果，则只需设置模式，然后它会给出递归函数。从中创建 DP。

对于您的问题，只需查看链接。它会解释一切

如需进一步的参考，请参阅 IOI 培训的链接

4 回答 4