POJ2411 Mondriaan's Dream 题解

Martian148 / 2024-01-30 / 原文

Question

POJ2411 Mondriaan's Dream

给出一个 $N\times M$ 的矩形，求用 $1\times 2$ 的小矩形铺满整个大矩形的方案数

Solution

轮廓线状压 DP

定义 $F[x][S]$ 表示枚举到第个格子，此时格子的轮廓线的状态为 $S$

现在要来讨论 $x$ 放或者不放，枚举上一个 $x$ 的状态 $k$

我们需要用 $k_5k_4k_3k_2k_1k_0 \rightarrow k_4k_3k_2k_1k_0x$

如果 $x$ 不放矩阵，那么要求 $k_5$ 必须为 $1$

如果 $x$ 放方块，横着放要求 $k_5$ 为 $1$，$k_0$ 为 $0$

如果竖着放，要求 $k_5$ 为 $0$

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
LL F[2][1<<11];
int main(){
    freopen("2411.in","r",stdin);
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF && n && m){
        if(n < m) swap(n,m);
        memset(F,0,sizeof(F));
        int now = 0, old = 1;
        F[now][(1<<m)-1] = 1;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                swap(now,old);
                memset(F[now],0,sizeof(F[now]));
                for(int k=0;k<(1<<m);k++){
                    if(k & 1<<(m-1))   // k的最高位为1，不放
                        F[now][(k<<1) & (~(1<<m))] += F[old][k];
                    if(i && !(k & 1<<(m-1)))  // k的最高位为0，竖着放
                        F[now][(k<<1)^1] += F[old][k];
                    if(j && (!(k&1)) && (k & 1<<(m-1)))  // k的最高位为1，且最低位为 0，横着放
                        F[now][((k<<1)|3) & (~(1<<m))] += F[old][k];
                }
            }
        printf("%lld\n",F[now][(1<<m)-1]);
    }
    return 0;
}