c - 動的プログラミングタイル

Question

http://www.spoj.pl/problems/GNY07H/ この質問では、2X1 のタイルを 4Xw (w >=1) の長方形に配置する方法をいくつか見つける必要があります。私はこの質問を試してみて、それに多くの時間を費やしましたが、解決策を思いつくことができませんでした. この種の問題へのアプローチ方法。それらの dp の再発を行う方法を意味します。?

score 11 · Accepted Answer

行ごとに 4xW の長方形を作成できます。次の行を作成するとき、前の行は 6 つの異なる状態になる可能性があります。

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

たとえば、前の行が (5) の場合、2 つの垂直ドミノを配置する必要があり、次の行は (3) になります。

XXXX
XABX
-AB-

X(W,q)最後の行が状態qにあり、残りが完全に塗りつぶされている4xWの長方形の可能な組み合わせを示すとします。

X(W-1,q)6つの状態すべてがわかっていれば、q簡単に計算できます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/;jsessionid=A5053396424C9F9BBB9337ECAC9C6C17?module=Thread&threadID=770579&start=0&mc=2#1643035 を適用する必要があることが記載されています」プロファイルを使用した動的プログラミング」、およびそのリンクはチュートリアルhttp://apps.topcoder.com/forums/?module=Thread&threadID=697369&start=0&mc=19、具体的には「レイヤーカウント+レイヤープロファイル」も指しています。

上記のリンクから: 「これは DP 状態ドメインの最もタフなタイプです。通常、特別なグラフの問題をタイリングまたはカバーするために使用されます。古典的な例は次のとおりです。長方形のボードをドミノでタイル化する方法の数を計算します (特定のセルは使用できません)。または、互いにぶつからないように、できるだけ多くのチェスの駒をチェス盤に置きます (ここでも、いくつかのセルが制限される場合があります)。

この手法に関するその他のより親しみやすいチュートリアルは、次の場所にあります。

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_13.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_7469.html

http://sk765.blogspot.in/2012/02/dynamic-programming-with-profile_6894.html

私もそれらを通して自分の道を進んでいます。

これは、あなたが尋ねた特定の質問に対する回答ではなく、このクラスの問題を解決するときに人々が従う一般的な手法です。