poj2411 Mondriaan‘s Dream状压DP

题目大意

给定高度和宽度的一个棋盘，现在要用高度为1，宽度为2的长方形覆盖这个棋盘，问方案数有多少

问题分析

• 初学状压DP，现在已经知道这道题是状压DP的问题了，关键在于如何状压呢？考虑到状压DP原理就是将状态压缩成二进制数，那么这个高度为1，宽度为2的长方形只有两种摆放方式，一种是横着放，另一种是竖着放，这样，可以规定，横着放的长方形两个格子里面都写1，竖着放的两个格子上面写0，下面写1，那么也就实现了状态压缩
• 因为一个格子只有两种状态，一种是0，另一种是1，所以如果说一行有$m$个格子，那么这一行的二进制状态一共就有$[0,2^m?1]$个总共$2^m$个，所以考虑枚举这所有的状态排除掉不合法的状态，这也就是先看自身的不合法，这只有一种情况那就是一行里面出现连续的1的次数为奇数，也就是该状态对应二进制数有连续奇数个1，判断程序如下

bool check1(int st){
    int bit = 0;while(st){
    if(st & 1) bit++;else{
    if(bit & 1) return false;else bit = 0;}st >>= 1;}if(bit & 1) return false;return true;
}

• 接下来需要考虑的是当前行和上一行之间是否冲突，通过这个考虑，可以看出这道题是要根据上一行来推断下一行的，也就是说具有最优子结构性质，印证了动态规划的合理性。如果说一行有$m$个数字，当前行和上一行要么都是1，要么一个0，一个1，不可能都是0，所以两行的状态取或结果必须为$2^m$，否则不合法；还有一种情况，如果出现$$\begin{gathered} 011 \\ 111 \end{gathered}$$这种情况，这其实是合法的，但是如果是这样$$\begin{gathered} 0111 \\ 1111 \end{gathered}$$那就不合法，怎么来判断这种情况呢？这里有一种非常巧妙的方法，如果设第一行状态为$st1$，第二行状态为$st2$，取$st1\&st2$，只要这个合法就合法了，这个判断程序如下

bool check2(int st1, int st2, int total){
    if((st1 | st2) != total - 1) return false;return ok[st1 & st2];
}

• 接下来开始状态转移，因为当前行可以通过上一行的状态转移过来，所以如果设$dp[i][st]$表示第$i$行状态为$st$的方案数，那么它可以从上一行状态为st1的$dp[i?1][st1]$转移过来，也就是$$dp[i][st]=dp[i][st]+dp[i?1][st1]$$$dp$入口处，也就是第一行的不同状态对应的方案数显然应该为1，预先处理所有的合法方案，完整程序如下

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
int Data[MAXN];
ll dp[15][1 << 11];
int ok[1 << 11];
bool check1(int st){
    int bit = 0;while(st){
    if(st & 1) bit++;else{
    if(bit & 1) return false;else bit = 0;}st >>= 1;}if(bit & 1) return false;return true;
}
bool check2(int st1, int st2, int total){
    if((st1 | st2) != total - 1) return false;return ok[st1 & st2];
}
int main(){
    int n, m;int total = (1 << 11);int num = 0;for(int i=0;i<total;i++){
    if(check1(i)) ok[i] = 1;}while(cin >> n >> m){
    if(n == 0 && m == 0) break;memset(dp, 0, sizeof dp);total = (1 << m);for(int i=0;i<total;i++){
    if(ok[i]) dp[0][i] = 1;}for(int i=1;i<n;i++){
    for(int j=0;j<total;j++){
    for(int k=0;k<total;k++){
    if(!check2(j, k, total)) continue;dp[i][j] += dp[i-1][k];}}}cout << dp[n-1][total - 1] << "\n";}return 0;
}