链接
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; }
|