POJ 2411: Mondriaan's Dream

题目链接：

题目大意：在$h \times w$（$1 \leqslant h,w \leqslant 11$）的网格中放满$1 \times 2$的木条，问有几种放置方案。

状压dp

定义横向放置的木条为$11$（横向），纵向放置的木条为$_1^0$（纵向）.

这样检查转移的合法性只需要检查前一行状态$s_{i-1}$与当前行状态$s_i$的位或（$s_{i-1}|s_i$）是否全为$1$，且横向的$1$是否均匹配.

定义状态$dp[i][s]$表示第$i$行状态为$s$的方案数，若状态$s_{i-1}$由状态$s_i$转移合法，则有$dp[i][s_{i-1}]+=dp[i-1][s_i]$.

最后一行不能放置向下的纵向木条，即最后一行全为$1$，故$ans=dp[n-1][(1<<m)-1]$.

可以预处理合法的状态并标记以降低复杂度。

总时间复杂度为$O(2^{MAX\{m\}}+n2^{2m})$.

代码如下：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 typedef long long ll; 5 int n,m; 6 ll dp[15][1<<11]; 7 bool s[1<<11]; 8 bool valid(int s){ 9     int tot=0;10     while(s){11         if(s&1)tot++;12         else if(tot&1)return 0;13         s>>=1;14     }15     return tot%2==0;16 }17 void init(){18     for(int i=0;i<(1<<11);++i)19         s[i]=valid(i);20 }21 bool check(int x,int y){22     if((x|y)+1!=(1<