题目链接

题意

用\(1\times 2\)的骨牌铺满\(H\times W(H,W\leq 11)\)的网格，问方案数。

思路

参考focus_best.

竖着的骨牌用\(\begin{pmatrix}0\\1\end{pmatrix}\)表示，横着的骨牌用\(\begin{pmatrix}1&1\end{pmatrix}\)表示。

则对于第\(i\)行，与之相容的第\(i-1\)行的状态需满足：

第\(i\)行是0的位置，第\(i-1\)行必须是1；
第\(i\)行是1的位置，第\(i-1\)行可为1可为0；如果是1则需满足，这样的连续的1的个数必为偶数（因为为横放）。

此外，

最后一行必为全1状态，

第一行需满足可以作为第一行的条件：这等价于，第一行的上一行可以表示为全1状态。

Code

#include <cstdio>

#include <cstring>

#include <iostream>

#define F(i, a, b) for (int i = (a); i < (b); ++i)

#define F2(i, a, b) for (int i = (a); i <= (b); ++i)

#define dF(i, a, b) for (int i = (a); i > (b); --i)

#define dF2(i, a, b) for (int i = (a); i >= (b); --i)

#define maxn 13

#define maxs 2100

using namespace std;

typedef long long LL;

int h, w; LL dp[maxs][maxn];

bool vis[maxs][maxn], hori[maxn];

bool check(int s1, int s2) {

    memset(hori, 0, sizeof hori);

    F(i, 0, w) {

        if (!(s2&(1<<i))) {

            if (!(s1&(1<<i))) return false;

        }

        else {

            if (s1&(1<<i)) hori[i] = true;

        }

    }

    int cont = 0; bool flag = false;

    F(i, 0, w+1) {

        if (!hori[i]) {

            if (cont&1) return false;

            cont = 0;

        }

        else ++cont;

    }

    return true;

}

LL dfs(int state, int row) {

    if (!row) {

        if (state==(1<<w)-1) return 1;

        else return 0;

    }

    if (vis[state][row]) return dp[state][row];

    vis[state][row] = true;

    LL temp=0;

    F(i, 0, 1<<w) {

        if (check(i, state)) temp += dfs(i, row-1);

    }

    return dp[state][row] = temp;

}

void work() {

    memset(vis, 0, sizeof vis);

    memset(dp, 0, sizeof dp);

    if (h<w) swap(h,w);

    printf("%lld\n", dfs((1<<w)-1, h));

}

int main() {

    while (scanf("%d%d", &h, &w) != EOF && h && w) work();

    return 0;

}

巴特西

poj 2411 Mondriaan's Dream 骨牌铺放状压dp

题目链接

题意

思路

Code

最新文章

热门文章

巴特西

poj 2411 Mondriaan's Dream 骨牌铺放 状压dp

题目链接

题意

思路

Code

最新文章

热门文章

poj 2411 Mondriaan's Dream 骨牌铺放状压dp