6

[SRM 209、Div I の 1000 点問題]

ある段階で、問題は次のようになります。

以下のように、任意の方法で回転できる 3 つの正方形ユニットのブロックが与えられた場合、与えられたサイズの長方形ブロックを埋める方法はいくつありますか。

| x | x |
| x |

たとえば、3x4 のブロックの場合、これらのブロックの配置方法は 4 通りあります。実際の解決策ではなく、この問題に対処する方法を探しています。方法の数を見つけるにはどうすればよいですか。それが発生する可能性は非常に多くあり、DP アプローチについてもサブの問題が重複しているとは思いません。

どんな洞察も大歓迎です。

4

1 に答える 1

-1

例外なく、L 字型のタイルを使用した空間の pxq ブロックのすべてのタイルは、L 字型のタイルのペアで構成される 2x3 ブロックのタイルに縮小されます。つまり、タイルは次のいずれかの形式です。

        xx      xx
        xy  or  yx  to form a vertical 2x3 block or
        yy      yy

        xyy       xxy
        xxy  or   xyy  to form a horizontal 3,2 block.

したがって、問題を 2x3 および 3x2 の長方形の「寄せ木張り」タイリングに減らすことができます。もちろん、不規則な非長方形の領域をタイル張りしている場合を除きます。その場合、L 字型のタイルを個別に考慮する必要があります。

于 2012-10-06T08:49:11.620 に答える