poj 2411(状压DP)

poj 2411
设$dp(i, j)$为第$i$行用$j$(状态)的方案总数，注意这里$j$不是编号就是状态！
然后先把行可行的方案标记，然后按行DP要注意，横着的砖是11，竖着的砖是竖着的01，所以($h[i] $或$h[i-1]$)必须全是$1$，不然就会有空隙，然后最重要的是要注意($h[i]$与$h[i-1]$)一定是可行方案，否则会出现“半个砖横向填充”的情况。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "poj2411"
using namespace std;
const int MAXN = 11 + 2;
int h, w, st[1<<MAXN];
LL dp[MAXN][1<<MAXN];//dp[i][j] 为第i行用j(状态)的方案总数 
bool check(int x) {
    int tot = 0;
    while (x) {
        if (x&1) tot++; else {
            if ((tot&1)==1) return false; 
            tot = 0;
        }
        x>>=1;
    }
    if ((tot&1)==1) return false; 
    return true;
}
bool check2(int s1, int s2) {
    return ((s1|s2)==(1<<w)-1) && (st[s1&s2]);
    //s1|s2必须是满的，不然有空隙
    //s1&s2必须是可行方案，否则会有横着摆的砖是奇数 
}
void clean() {
    ms(st, false), ms(dp, 0);
}
void solve() {
    clean();
    if (w>h) swap(h, w);
    for (int i=0;i<(1<<w);i++) if (check(i)) st[i] = true;
    for (int i=0;i<(1<<w);i++) {
        if (st[i]) dp[1][i] = 1;
    }
    for (int hi=2;hi<=h;hi++) {
        for (int i=0;i<(1<<w);i++) {
            for (int j=0;j<(1<<w);j++) {
                if (dp[hi-1][j]==0) continue;
                if (check2(i, j)) {
                    dp[hi][i] += dp[hi-1][j];
                }
            }
        }
    }
    printf("%lld\n", dp[h][(1<<w)-1]);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
    #endif
    while (scanf("%d%d", &h, &w)==2&&h&&w) solve();
    fclose(stdin); fclose(stdout);
    return 0;
}