「POJ 2411」Mondriaan's Dream

题目链接:POJ 2411

Description

给定一个$n\times m$的方格图,求有多少种可以$1\times 2$牌覆盖的方案数。

牌可以翻转

Data Range

$1\leq n,m\leq 11$

Solution

考虑轮廓线$DP$,定义状态为$f[i][j][sta]$表示当前在$(i,j)$格子,左上角的轮廓线的状态为$sta$,并且最后一个牌的左下角覆盖的格子为$(i,j)$的方案数。

初始值:$f[1][1][full]=1$,因为上面都放不了牌,就当做是满的状态。

考虑$f[i][j][sta]$从上一个格子转移(逆推)

一共有以下$4$种情况:0表示没被覆盖,1表示被覆盖了,*表示我们当前考虑的$(i,j)$,&表示不在轮廓线上的点。

Case 1

&0
0*

画图可知$*$左边的$0$是当前轮廓线二进制下第$j-1$位,上方的为第$j$位。

很明显$*$上的$0$必须要被覆盖掉,不然就覆盖不了了,也就是第$j$位上的点必须要被覆盖掉,那么原来第$j$位上的$0$就变成了$1$。

假设上一个格子的状态为$lastSta$,那么现在这个格子$(i,j)$的状态就是$(lastSta|(1<<j))$,其中满足$lastSta$的第$j$位为$0$

Case 2

&0
1*

这种情况同Case 1,也是这一个格子只能竖着放。

Case 3

&1
0*

现在已经不存在上面是$0$的情况了,也就是现在轮廓线上第$j$位一定是$1$了。

这个时候我们可以考虑向左覆盖,那么原状态$lastSta$第$j-1$位为$0$,转移过来之后$j-1$和$j$位已经是$1$了,所以我们$(i,j)$轮廓线的状态为$(lastSta|(1<<(j-1)))$

第二种情况:不放,那么轮廓线上的第$j$为就变成了$0$。

Case 4

&1
1*

这种情况就是Case 3的不放情况。

Code

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define REP(i, s, t) for (int i = (s); i <= (t); i ++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> void chkmax(T &x, T y) { x = x > y ? x : y; }
template <typename T> void chkmin(T &x, T y) { x = x < y ? x : y; }
template <typename T> void read(T &x) {
    x = 0; bool w = 0; char ch = 0;
    for (; !isdigit(ch); ch = getchar()) w |= ch == '-';
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= w ? -1 : 1;
}
template <typename T> void write(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
template <typename T> void write(T x, char ch) {
    write(x); putchar(ch);
}
const int N = 12;
ll f[2][1 << N];
int n, m;
int main() {
    while (~scanf("%d%d", &n, &m) && n && m) {
        memset(f, 0, sizeof(f));
        f[0][(1 << m) - 1] = 1; 
        int cur = 1;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                cur ^= 1;  
                for (int sta = 0; sta < (1 << m); sta ++) {
                    if (f[cur][sta]) {
                        if (!(sta >> j & 1)) {
                            int nxtSta = sta | (1 << j); 
                            f[cur ^ 1][nxtSta] += f[cur][sta];
                        }
                        else {
                            if (j > 0 && !(sta >> (j - 1) & 1)) { // left is empty
                                int nxtSta = sta | (1 << (j - 1)); 
                                f[cur ^ 1][nxtSta] += f[cur][sta];
                            }
                            int nxtSta = sta ^ (1 << j); 
                            f[cur ^ 1][nxtSta] += f[cur][sta]; 
                        }
                    }
                }
                memset(f[cur], 0, sizeof(f[cur]));
            }
        }
        write(f[cur ^ 1][(1 << m) - 1], '\n'); 
    }
    return 0;
}
最后修改:2019 年 07 月 30 日 11 : 08 AM
如果觉得我的文章对你有用,请随意赞赏

发表评论