又是一道经典的状态压缩dp

开始自己想了一下，总是觉得因为这个小矩形可以竖着放导致没法确定状态如何转移(第i行的小矩形如果竖着放,及可能影响i-1行,也有可能影响i+1行);后面看了别人的题解后，才知道原来我们可以固定小矩形竖着放的时候只能向前放，这样第i行的状态就只能影响i-1行了，也就能顺利的写出状态转移方程啦。

设dp[i][j]表示第i行处于状态j的时候，共有多少种放置方法。

dp[i][j]=sum(dp[i-1][k]),其中状态j和k要能共存,并且j和k要使得第i-1行刚好铺满。

然后就是初始化，初始化时我们将第一行有连续偶数个1的状态赋值为1(因为第一行没有上一行，是不可能出现竖放情况的)其余所有状态为0。

这个题目中较难处理的就是状态转移中j和k必须共存，并且j和k要使得第i-1行刚好铺满的这个条件。

代码中是以j状态为主然后去判断k状态，其实也可以反过来的；具体的处理见代码。

当然这个题目如果就这样赤裸裸的交是会超时的，还可以加点优化：

1）如果n*m为奇数，则是不可能拼凑成功的(因为小矩形的面积是偶数)

2) 总是取n,m中小的那个当成m，这样可以减少状态总数。

3) 因为n,m很小,输入的状态中应该有重复的，所以我们可以把每次的答案记录下来，下次遇到相同的输入时直接输出答案。

还有就是注意一下位运算的优先级(多加括号).

?

代码如下：

?

?

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; long long dp[12][3300]; long long ans[12][3300]; int n,m; bool init(int x) { for(int i=0;i
      
       
?