POJ 2411. Mondriaan‘s Dream

发表于 分类于

链接

http://poj.org/problem?id=2411

题意

求把 $nm$ 的棋盘分割成若干个 $12$ 的的长方形有多少种方案

思路

状压 DP

对于每一行设某单位格是竖着的 $1*2$ 的长方形的上半部分的状态为 $1$，其余状态为 $0$

对于下一行，如果上行状态为 $1$ 的单元格该行都为 $0$，即上行状态与该行状态按位与值为 $0$，则可以转移

与上行按位或后，代表该行所有是竖着的长方形的下半部分的单位格匹配成功，那么剩下的 $0$ 肯定是横着的长方形，所以每个 $0$ 段必须是偶数段

预处理每个状态的 $0$ 段是否都是偶数段

然后枚举 $2^m$ 个状态转移即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
bool st[1<<11];
ll f[12][1<<11];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n>>m&&n) {
        for(int i=0;i<1<<m;i++) {
            int cnt=0;
            int fg=0;
            for(int j=0;j<m;j++) {
                if(i&(1<<j)) {
                    if(cnt&1) fg=1,cnt=0;
                    if(fg) break;
                }
                else cnt^=1;
            }
            st[i]=fg|cnt?false:true;
        }
        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++)
                    if(!(k&j)&&st[k|j])
                        f[i][j]+=f[i-1][k];
            }
        cout<<f[n][0]<<endl;
    }
    return 0;
}