DP专题8 | 骨牌摆放问题 POJ 2411（状态压缩DP）

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

long long f[12][1 << 11];
int in_s[1 << 11];

// 注意这里一定要用64位的整数
long long solve(int n, int m) {
    for (int i = 0; i < 1 << m; ++i) {
        int cnt = 0, has_odd = 0;
        // 遍历m中的每一位
        for (int j = 0; j < m; ++j) {
            if (i >> j & 1) {
                //把cnt的值先存放到has_odd上，然后清零
                has_odd |= cnt, cnt = 0;
            } else {
                //如果是偶数个0，则肯定cnt最后为0，因为0^1=1 1^1=0
                cnt ^= 1;
            }
        }
        // 如果cnt=1则表明存在连续的奇数个0位
        in_s[i] = has_odd | cnt ? 0 : 1;
    }

    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 1 << m; ++j) {
            f[i][j] = 0;
            for (int k = 0; k < 1 << m; ++k) {
                // 上面是1下面必须是0
                // 0必须是连续偶数个
                if ((j & k) == 0 && in_s[j | k]) {
                    // 满足要求后加上i-1行k的所有情况
                    f[i][j] += f[i - 1][k];
                }
            }
        }
    }

    // 最后一行的j所有位都是0
    return f[n][0];
}

int main() {
#ifdef __MSYS__
    freopen("test.txt", "r", stdin);
#endif

    int n, m;

    while (cin >> n >> m && n) {
        cout << solve(n, m) << endl;
    }
    return 0;
}