传送门：

Mondriaan's Dream

题目简述

有一个\(W\)行\(H\)列的广场，需要用\(1*2\)小砖铺满，小砖之间互相不能重叠，问

有多少种不同的铺法？

输入数据：

只有一行\(2\)个整数，分别为\(W\)和\(H\)，\((1<=W,H<=11)\)

输出数据：

只有\(1\)个整数，为所有的铺法数。

---

妥妥状压

我们向上或者向右放砖头。

为什么呢？

令\(dp[i][j]\)代表\(i\)行\(j\)状态的方案数（\(j\)中的\(1\)代表这个位置在此行时是否被覆盖，不论它是被自己或者别人覆盖的）

此时当前行的\(0\)即可以约束下一行，向上放的过程。向右放即在本行处理。

处理的时候小心一点

code

#include 
    
     #include 
     
      #define ll long longconst int N=12;ll dp[N][1<
      
       >(m-dep)&1);//是否需要看上一行的    if(is&&!flag)        dfs(line,l_li,dep+1,0,tt<<1|1);//被上一个看且不看上一行    if(!is&&flag)        dfs(line,l_li,dep+1,0,tt<<1|1);//没被上一个看且要看上一行    if(!is&&!flag)    {        if(dep!=m) dfs(line,l_li,dep+1,1,tt<<1|1);        dfs(line,l_li,dep+1,0,tt<<1);    }//没被上一个看且不看上一行}int main(){    scanf("%d%d",&n,&m);    while(m!=0&&n!=0)    {        memset(dp,0,sizeof(dp));        dp[0][(1<
      
     
    

---

2018.5.10