固定楼层算法

Question

好吧,我有这个任务:John的浴室地板坏了.我们有一张这个楼层的地图,其中'.' 是好板,'+'是坏板,例如:

.+++
.+.+

在这里,我们有5个破碎板和3个好板.有两种板材,在商店出售:1x1板和2x1板.1x1板材成本A和2x1板材成本B.任务是:给出地板图,计算地板固定的最低价格.

以顶部为例:我们可以放置2个2x1板和1个1x1板.因此,价格将是A + 2*B.

我有一个想法:每个破碎的板数计算连接断板的最大长度.然后价格是长度/ 2*B +长度%2*A.

问题是,我真的不知道该怎么做.我有一些递归算法的想法,但也有那么像圈诸多问题:

+++
+.+
+++

所以我有两个问题:

1. 我正朝着正确的方向前进吗？
2. 你能给我一些关于实现这个算法的提示吗？

谢谢!

编辑

当2*A <B时有一些小问题,但让我们谈谈非平凡=)

/编辑

Answer 1

经典的平铺问题。这是一个加权精确覆盖，在不平凡的情况下（当使用两个 1x1 瓷砖比使用一个 1x2 瓷砖成本更高时）我会使用 ZDD 来解决它。请参阅计算机编程艺术 V4 1B中的示例（棋盘上的多米诺骨牌）。

有一些可用的库（例如 CUDD），因此您不必从头开始实现 ZDD，尽管这也不是太难。

作为奖励，您还可以获得其他算法通常不提供的其他信息，例如有效平铺的数量，而无需全部枚举。它还可以轻松推广到其他尺寸/形状的瓷砖（3x1、2x2、L 形件等）。