挺简单的一道题，由于自己很少做这类型的题目，做出来还是挺有感觉的。

    每一个木块只有两种摆放方式，用0 ， 1表示，0表示横放，1表示竖放，所以每一行，必须要有连续偶数个0，而且最后一行不能有1。若这一列对应的上一行有1，则这一列不能为1，但是计算的时候要把这一列看成1，若对应可放，则可以加上所对应的值，由于每一个状态可以对应多个可行状态，所以要递推累加。最有结果为dp[h][0]。

1

#include

<

iostream

>

2

#include

<

cstdio

>

3

#include

<

algorithm

>

4

5

 

using

namespace

std;

6

7

typedef

long

long

LL;

8

const

int

maxn

=

(

1

<<

12

);

9

10

LL h , w , dp[

12

][maxn];

11

12

bool

judge(LL s)

13

{

14

LL cnt

=

0

;

15

for

(LL i

=

0

; i

<

w; i

++

)

16

{

17

LL t

=

s

&

1

;

18

if

(t)

19

{

20

if

(cnt

&

1

)

21

return

false

;

22

else

23

cnt

=

0

;

24

}

else

25

cnt

++

;

26

s

>>=

1

;

27

}

28

if

(cnt

&

1

)

29

return

false

;

30

return

true

;

31

}

32

33

int

main()

34

{

35

while

(

~

scanf(

"

%lld %lld

"

,

&

h,

&

w))

36

{

37

if

(h

==

0

&&

w

==

0

)

38

break

;

39

memset(dp ,

0

,

sizeof

(dp));

40

for

(LL i

=

0

; i

<

(

1

<<

w); i

++

)

41

{

42

if

(judge(i))

43

{

44

dp[

1

][i]

=

1

;

45

}

46

}

47

for

(LL i

=

2

; i

<=

h; i

++

)

48

{

49

for

(LL j

=

0

; j

<

(

1

<<

w); j

++

)

50

{

51

for

(LL k

=

0

; k

<

(

1

<<

w); k

++

)

52

{

53

LL t

=

j

&

k;

54

if

(t)

55

continue

;

56

t

=

j

|

k;

57

if

(judge(t))

58

{

59

dp[i][j]

+=

dp[i

-

1

][k];

60

}

61

}

62

}

63

}

64

printf(

"

%lld\n

"

, dp[h][

0

]);

65

}

66

return

0

;

67

}

68