http://poj.org/problem?id=2411
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.
http://luoshaochuan.com/2017/07/15/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93(%E5%85%AD%EF%BC%89/
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!
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.
Sample Input
1 2 1 3 1 4 2 2 2 3 2 4 2 11 4 11 0 0
Sample Output
1 0 1 2 3 5 144 51205
这个题目类属于状态压缩DP，对于状态压缩DP，其实最简单的理解就是把状态用比特位的形式表示出来，我们会在下面用例子来说明。
假如现在我们在铺砖 位置(i, j), 并且假设之前的位置已经铺设好的了，在这个位置，我们的选择：
1. 不用铺砖了，可能在(i-1, j)的时刻已经被竖着铺上了，然后考虑的是（i， j+1）
2. 横铺砖，将(i, j+1）也铺上了，然后考虑的是(i, j+2)
3. 竖着铺砖，（将i，j）和（i+1，j）铺上一个竖立的转头。
所以我们如下翻译我们的选择，在位置(i, j) 如果我们选择横着贴砖，那么将(i, j), (i, j+1)都填写成1， 如果竖着贴砖，我们将(i,j)填写成0， 将(i+1, j)填写成1.
为什么要这么计数呢，我觉得应该这样理解：
1. 在横着贴砖的时候，(i, j), (i, j+1) 都是1，这个值其实对下一行如何选择没有影响。
2. 竖着贴砖的第二个，我们也选择了1， 因为这个砖头结束了，对下一行如何选择依然没有影响。
3. 而竖着的第一个砖头，这个砖头是对下面有影响的，如果(i,j)是0，那么(i+1, j)只有是1的情况下才能满足条件。
（这涉及到接下来的 状态兼容性问题）
对于竖着贴砖为什么这样选择，这样选择的一个好处是，我们在处理最后一行的时候，可以保证最后一行都是1， 因为最后一行绝对不能成为 竖砖开始，所以很容易取得最后的解。
好了，我们把这样理解的方案画成图：
如果我们将每一行都理解成一个二进制数字，那么
Row1 = 51, Row2 = 15, Row3 = 48, Row4 = 63, Row5 = 51, Row6 = 63.
最后转头铺满的状态，一定是最后一行全是1。
我们用DP(i,j) 表示如下含义： 当第i行，达到状态j的时候，所能采取的方案数目。 所以明显我们的最后目的是求 DP(N, 2^(M-1)-1);
我们再来简单的分析一下为什么问题可以满足动态规划， 加入现在分析的对象是 DP(i,j)， 那么这一行有多少种铺设办法是和上一行相关的，
如果上一行的某个状态DP(i-1,k) 可以达到 DP(i, j) 我们认为这两个状态是兼容的，如果DP(i-1,k)和DP(i, j)兼容并且 DP(i-1, k)有S中铺设方案，那么DP(i, j)就可以从DP(i-1, k)
这条路径中获得S个方案。 当然这里k的取值可以是 0 ~~~~ 2^(M-1) -1种取值。
现在我们来理解一下，什么叫做 j, k 兼容。
其实我们在上面已经基本给出分析， 如果我们现在铺设 (i,x) x这里表示第i行，第x列
1. 如果值 i 行，j 在x位上的值是0， 那么第 i-1行，j的值在x位上一定是1。因为不可能在同一列相邻的位置铺两个竖着的 第一个，如果满足下一步测试的是(i, x+1), 否则直接返回不兼容。
2. 如果值 i 行，j在x位置的值是1 .
{
那么有可能有两种情况：
1. (i-1, x)是0， 这个时候一定是竖着铺设了，下一步检测的是(i, x + 1)
2. (i-1, x) 是1， 如果是这样的话，那么(i, x)一定是要选择横着铺了，那么(i,x+1)也一定是1，并且(i-1, x + 1)一定是1（如果是0，就是竖着铺了），如果不满足就返回不兼容，满足条件 就测试(i, x + 2)
}
对于第一行的兼容性，我们要做一下特别的分析，在第一行中，要么放0， 要么放1。
加入当前测试的是 DP(0, j)的第 x的比特位，即第0行，x列
1. 如果x是1，那么 x + 1 也一定是1，然后测试到 x + 2
2. 如果x是0， 那么直接测试下一个 x + 1
首先还是状态的表示，用0表示没有放木块，用1表示放了木块。此外，对于一个横放的木块，对应的两位都用1表示；对于一个竖放的木块，第一行用1表示，第二行用0表示。这只是一种设状态的方式，当然还有别的设法，但是这种方法在接下来就会发现优点。
状态表示完就要处理转移了，如何判断一个转移是否合法比较难办，用一个dfs却可以简洁的解决这个问题。
对于上一行到下一行的转移，规定上一行一定填满，这样有三种方式：
dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
第一种上面是1，那么下面一定是0，表示是一个竖放的木块。
第二种上面是0，就是说这个位置一定是一个竖放木块的下半截，那么下一行肯定是要另起一行了，放一个竖放或者横放的木块都必须是1。
第三种相当于上下两行各放一个横木块。
实现的时候我用了一个vector记录每个状态所有可行的转移，这样在dp的时候可以加快一些效率。
对于上一行到下一行的转移，规定上一行一定填满，这样有三种方式：
dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
第一种上面是1，那么下面一定是0，表示是一个竖放的木块。
第二种上面是0，就是说这个位置一定是一个竖放木块的下半截，那么下一行肯定是要另起一行了，放一个竖放或者横放的木块都必须是1。
第三种相当于上下两行各放一个横木块。
实现的时候我用了一个vector记录每个状态所有可行的转移，这样在dp的时候可以加快一些效率。
还有一个问题需要考虑，那就是初值和最终的结果。如果寻找合法状态，依然比较麻烦，假设共有n行，可以分别在这n行上下新加两行。下面一行都是1，由于第n行肯定要填满，这样新加的全1的行就相当于顶住了第n行使其没有凸出（有凸出那么第n+1行有0），而通过第n行到第n+1行转移保留了所有合法状态；同理最上面加的那行保证第一行没有凸出。最后第n+1行对应全1的状态就是最终的结果了。通过新加行巧妙地解决了初值和终值。
实现的时候也需要注意一下，在TSP问题中，外层循环是状态，内层是点，之所以这样写因为在枚举点的时候，可能会从比当前编号大的点转移，但是由于无论怎样转移过来的状态肯定比当前状态小（去掉了1），所以先从小到大枚举状态就保证转移过来的状态一定是算过的。而这个题目里面正好反过来，因为状态可能从比当前状态大的状态转移过来，而行数肯定是从编号小的行转移，因此先枚举行就能保证转移过来的状态一定是更新过的。
/* f[i][j]表示第i行，方格排布为二进制数j（第k位上为1表示凸出一个格子，为0表示不凸出）
的方案数。用DFS进行状态转移。*/
static long f[][]=new long[12][2048];
static int n, m;
static void dfs(int i, int j, int jj, int s)//j是初始状态，jj是目标状态.s表示列数
{
if (s == m)//把i行m列放好
f[i + 1][jj] += f[i][j];//等于I+1行被占去的格子的2进制为JJ应该可以多放f[i][j]的方略
else if ((jj & (1 << s)) == 0)//表示第J列能放1/0
{
dfs(i, j, jj | (1 << s), s + 1);//放1
if (s < m - 1 && (jj & (1 << (s + 1))) == 0) dfs(i, j, jj, s + 2);//放0（横占2格）
}
else//表示此处只能放0
dfs(i, j, jj & ~(1 << s), s + 1);//(jj & (1 << s)这个位置已经被占
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
while (sc.hasNext())
{
n=sc.nextInt();
m=sc.nextInt();
if(n+m==0) break;
for(int i=0;i< f.length;i++)
Arrays.fill(f[i],0);
f[0][0] = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < (1 << m); j++)
if (f[i][j]!=0) //剪枝（为0没有必要考虑）
dfs(i, j, j, 0);
System.out.printf("%d\n", f[n][0]);//不占n行也即0~n-1放满的方法数
}
}
}
http://luoshaochuan.com/2017/07/15/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93(%E5%85%AD%EF%BC%89/
如果用一个数字j的二进制各位x来表示该位置铺瓷砖的方法，如果x位置横着放瓷砖，则x位和x+1位都置1;如果x为竖着放，则x位置0，下一行的x位置1。令dp[i][j]表示第i行达到状态j的填充方案数。则dp[i][j]等于所有与其兼容的dp[i-1][k]之和，所谓兼容，指的是如果第i-1状态k的x位置出现0，则i行x位置必须为1。例如第i行为11，则第i-1行可以为00或11，它们都是可以被第i行的11兼容。
对于位置[p,q],我们可以选择横着放瓷砖，也可以选择竖着放瓷砖，我们可以递归的产生所有合法状态。
对于位置[p,q],我们可以选择横着放瓷砖，也可以选择竖着放瓷砖，我们可以递归的产生所有合法状态。
当前位不放，则前行的当前位必定为1才能兼容且后行为0：c=c+1，(pre<<1)|1,now<<1
当前位上方，则前行的当前位必定为0才能兼容且后行为1：c=c+1，(pre<<1),(now<<1)|1
当前位右方，则前行的当前2位必定为1才能兼容且后行当前2位为1：c=c+2，(pre<<1)|3,(now<<1)|3
|
|
