用1×2のタイルカバー8×8の床は、どのような方法がありますか?
この問題はPOJにあります.住所は:http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
以前この問題をやったことがありますが、状態DPでやったのです.大まかに言えば,DPは2次元を用い,1次元はどの行に到達するか,もう1次元はその行の状態を表す.
バイナリで表す
格子をN行M列とする.
表示方法は次のとおりです.
f[i][j]. ---- iはi行目、jはその行のバイナリ状態を表す.一方、f[i][j]は、i,jからなる状態が何種類あるかを記録する.
例を挙げて、全部で4行5列あると仮定します.
*番号はブロックが敷かれていることを示し、0はブロックが敷かれていないことを示します.
*****
*0**0
00000
00000
2行目の状態は*0**0、すなわちバイナリで表すと10110、すなわちf[2][22]で表されることがわかる.(もちろん、行番号は0からでも計算できます)
以上が状態表示方法であり,状態表示方法があれば後で状態遷移を行う繰返し式を得る必要がある.
i行j列のその格子を考えると、3つの状態があり、1つ目はi-1行j列目で敷かれ、2つ目は本行内で隣接する格子と敷かれたタイルで、3つ目はこの格子を空にして次の行に備えて使用される.
この行の格子の各状態を列挙すると、所望の前の行の状態が得られる.
たとえば、次のような状態を列挙します.*は格子が充填されていることを示します.-スペースを表し、残りの数字は2*1のタイルの配置を表します.
1***3**
1-22344
本行の状態は1011111であり、この状態を生成するために必要な前の行の状態は、0111011であることがわかる.タイル1とタイル3の埋め込みを満たすことができ、スペースが残らないからである.
従って、第2次元であるa[i][1011111]+=a[i-1][0111011]をバイナリで表すことで、本状態から一度加算することができる.
では、最後にa[N][(1<POJのこの問題のコード(数年前に書いた、スタイルが腐っていて、笑った):
C/C++ code
2953784 zyl072 2411 Accepted 7844K 124MS G++ 1222B 2007-11-29 10:22:08
ちょっと説明が必要ですが、この問題はテストデータが多いので、私は毎回入力してから計算をやり直すのではなく、入力可能なすべての結果を一度に全部計算することを選びました.そして、入力してから直接結果を出力することができます.これにより、テストデータが多い場合に多くの繰り返し演算を避けることができます.そのため、私のDP状態は3次元で表されています.行、列、現在の行のステータスではありません.
転載:http://topic.csdn.net/u/20100621/16/74D19159-8921-4405-8028-73B348755716.html
以前この問題をやったことがありますが、状態DPでやったのです.大まかに言えば,DPは2次元を用い,1次元はどの行に到達するか,もう1次元はその行の状態を表す.
バイナリで表す
格子をN行M列とする.
表示方法は次のとおりです.
f[i][j]. ---- iはi行目、jはその行のバイナリ状態を表す.一方、f[i][j]は、i,jからなる状態が何種類あるかを記録する.
例を挙げて、全部で4行5列あると仮定します.
*番号はブロックが敷かれていることを示し、0はブロックが敷かれていないことを示します.
*****
*0**0
00000
00000
2行目の状態は*0**0、すなわちバイナリで表すと10110、すなわちf[2][22]で表されることがわかる.(もちろん、行番号は0からでも計算できます)
以上が状態表示方法であり,状態表示方法があれば後で状態遷移を行う繰返し式を得る必要がある.
i行j列のその格子を考えると、3つの状態があり、1つ目はi-1行j列目で敷かれ、2つ目は本行内で隣接する格子と敷かれたタイルで、3つ目はこの格子を空にして次の行に備えて使用される.
この行の格子の各状態を列挙すると、所望の前の行の状態が得られる.
たとえば、次のような状態を列挙します.*は格子が充填されていることを示します.-スペースを表し、残りの数字は2*1のタイルの配置を表します.
1***3**
1-22344
本行の状態は1011111であり、この状態を生成するために必要な前の行の状態は、0111011であることがわかる.タイル1とタイル3の埋め込みを満たすことができ、スペースが残らないからである.
従って、第2次元であるa[i][1011111]+=a[i-1][0111011]をバイナリで表すことで、本状態から一度加算することができる.
では、最後にa[N][(1<
C/C++ code
#include
<
stdio.h
>
#include
<
string
.h
>
long
long
s[
14
][
14
][
5000
];
int
w,h;
int
list[
20
],v[
20
];
void
GetList(
int
step){
if
(step
>
w){
int
value1
=
0
;
int
value2
=
0
;
int
i;
for
(i
=
1
;i
<=
w;i
++
){ value1
<<=
1
; value2
<<=
1
;
switch
(list[i]){
case
0
: value1
|=
1
;
break
;
case
1
: value1
|=
1
; value2
|=
1
;
break
;
case
2
: value2
|=
1
;
break
; } }
if
(h
>
1
) s[w][h][value2]
+=
s[w][h
-
1
][value1];
else
s[w][h][value2]
=
1
;
return
; }
if
(h
>
1
) list[step]
=
2
,GetList(step
+
1
);
if
(step
<
w) list[step]
=
list[step
+
1
]
=
1
,GetList(step
+
2
); list[step]
=
0
; GetList(step
+
1
); }
int
main(){ memset(s,
0
,
sizeof
s);
int
i,j,k; v[
0
]
=
1
;
for
(i
=
1
;i
<
20
;i
++
) v[i]
=
v[i
-
1
]
<<
1
;
for
(w
=
1
;w
<=
12
;w
++
)
for
(h
=
1
;h
<=
12
;h
++
) GetList(
1
);
for
(scanf(
"
%d%d
"
,
&
w,
&
h);w;scanf(
"
%d%d
"
,
&
w,
&
h)) printf(
"
%I64d
"
,s[w][h][v[w]
-
1
]); }
2953784 zyl072 2411 Accepted 7844K 124MS G++ 1222B 2007-11-29 10:22:08
ちょっと説明が必要ですが、この問題はテストデータが多いので、私は毎回入力してから計算をやり直すのではなく、入力可能なすべての結果を一度に全部計算することを選びました.そして、入力してから直接結果を出力することができます.これにより、テストデータが多い場合に多くの繰り返し演算を避けることができます.そのため、私のDP状態は3次元で表されています.行、列、現在の行のステータスではありません.
転載:http://topic.csdn.net/u/20100621/16/74D19159-8921-4405-8028-73B348755716.html