洛谷原题链接：P10975 Mondriaan's Dream
看数据范围容易发现是状压DP
考虑如何规定状态
设f(i,s)为第i行，填充格式为s的方案数，其中s为二进制数，1表示在这个位置填充一个长方形并使它延伸到i+1（即以i为起点的两行一列的长方形），0表示由i-1延伸而来或填充一个长方形并使它不延伸到i+1（即在第i行放置一行两列的长方形）
转移方程很简单，dp（i，s1）= dp(i-1, s2)+1,关键在于如何判断 s1和s2是否合法
合法性判断：
- 如果i-1的第j位为1，代表j是一个延伸到i的长方形，所以i的第j位就一定是由i-1的第j位填充的,即 s1 & s2 == 0
- 对于s1，被s2填充延伸部分填充之后，不能存在一段连续奇数个0的序列（无法使用两格的长方形填充），即 s1 | s2 之后判断
// x=s1 | s2;
// w=s1.size();
bool check(int x,int w)
{bool flag=0;for(int j=0;j<w;j++){if(!((1<<j) & x)){if(!flag) flag=1;else flag=0;}else if(flag) return 0;}if(flag) return 0; return 1;
}
- 考虑边界的判断，即当i=n时,s1只能等于0（无法向后面延伸）
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N=(1<<11);
int dp[12][N];
int n,m;bool check(int x,int w)
{bool flag=0;for(int j=0;j<w;j++){if(!((1<<j) & x)){if(!flag) flag=1;else flag=0;}else if(flag) return 0;}if(flag) return 0; return 1;
}int sovle (int h,int w)
{if(h==1){if(w%2) return 0;else return 1;}int res=0;memset(dp,0,sizeof(dp));for(int i=0;i<(1<<w);i++) if(check(i,w)) dp[1][i]=1;for(int i=2;i<=h;i++){for(int now=0;now<(1<<w);now++){for(int bs=0;bs<(1<<w);bs++){if(now & bs) continue;if(!check((now | bs),w)) continue;dp[i][now]+=dp[i-1][bs];}if(i==h) break;}}for(int i=0;i<(1<<w);i++) res+=dp[h][i];return res;
}signed main(){cin>>n>>m;while(n or m){cout<<sovle(n,m)<<endl;cin>>n>>m;}return 0;
}