# 状态压缩总结

## 引言

（来自网络

Lsh 是左移 Rsh 是右移 RoL 是右移1 RoR 是左移1

## 正文

#### 例2

poj 3254 Corn Fields

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

2 3
1 1 1
0 1 0

9

（翻译来自luogu

i表示当前行，j表示当前行的情况，k表示上一行的情况

poj 1185 炮兵阵地

Description

Input

Output

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output

6

nu中存的是这一行中能放炮的数量

### poj 2411 Mondriaan’s Dream

#### Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series’ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.

Expert as he was in this material, he saw at a glance that he’ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won’t turn into a nightmare!

#### Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

#### Output

For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

1
0
1
2
3
5
144
51205

To be continued…

×