POJ 2411 Mondriaan's Dream (状压DP)

dp[i][j]表示第i行 为j 状态的有多少种方法。

就要写一个匹配的函数，保证上一行可以跟这一行凑出来合法的满满的两行。

1、如果第i行中有0，则第i-1行一定为1；

2、如果第i行中为1的x列第i-1行为0，说明第i行肯定是竖着放的；

3、如果第i行中为1的x列第i-1行的该列也为1，可能性只有一个，第i行是横放的，所以第i行的x+1列也必须为1，又因为第i行的x+1列为1是因为横着放的，所以第i-1行的x+1列也必须为1。

那么状态转移就很简单了。

dp[i][cur] += dp[i-1][last] 如果last和cur能匹配的话。

还有输出的时候为什么是输出dp[n][1<

因为你在这一行是1 上一行是0 等同于这一行是0 上一行是 1

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       typedef long long LL; using namespace std; LL dp[11][1<<11]; int n,m; bool ok(int x) { int pos=1; int count=0; for(int i=0;i<(1<