题目大意：有一个W行H列的广场，需要用1*2小砖铺盖，小砖之间互相不能重叠，问有多少种不同的铺法？

(w,h<=11)

Solution:

状态压缩DP。

爆搜肯定是不行的，由于每个点有2种状态（放，不放），那随随便便搜索树上的节点就超过2^121了，GG。

我们考虑按行铺，每行的状态多可以表示为一个01串，每行的状态s都是通过前一行的状态s'转移来的，用dp[i][state]来表示第i行状态为state的方案数，因此我们考虑用dfs来实现会方便很多。

尝试再分析一下问题的性质，对于i行j列

如果前一行该位置为0,那么该位置可以竖放 即 0-> 1

如果前一行连续两个位置为0,那么这两个连续位置可以横放 即00-> 11

如果前一行该位置为1,显然该位置不能再放,于是应该把该位置设置为0 ，即1-> 0

对于一个当前行的可行状态s，用dfs构造不和它矛盾的下一行的状态，将方案累加到下一行。 所以每遇到一个可行状态，都要进行一遍dfs。

#include
    
     using namespace std;int w,h;long long s,dp[13][15000];  //第i行 状态为j inline void dfs(int i,int state,int next,int c)//i行 i行的状态 下一行的状态  c-1列 {    if(c==h)    {        dp[i+1][next]+=dp[i][state];        return;    }    if((state&(1<
     
      >w>>h;    if(w*h%2==1)    cout<<"-1";    s=(1<