经典的状压DP
题目描述
把N*M的棋盘分割成若干个1*2的的长方形,有多少种方案。
输入样例
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0
输出样例
1
0
1
2
3
5
144
51205
分析
我们应该明确这个状态怎么设计,我们枚举每一个状态,如果要横着放,那0(代表横放)的个数是一个偶数,
于是我们就可以筛出合法的状态,同时在枚举这一层的状态时,还要关注上一层的状态,毕竟如果上一层竖放
的话有一部分就会与这一层冲突,所以要保证当前这一层的状态与上一层的状态不冲突且合法
C++ 代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=12,M=1<<N;
int n,m;
ll f[N][M];
bool sd[M];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if((!n)||(!m)) break;
for (int i=0;i<1<<n;i++)
{
sd[i]=true;
int cnt=0;
for (int j=0;j<n;j++)
{
if(i>>j&1)
{
if(cnt&1) sd[i]=false;
cnt=0;
}
else cnt++;
}
if(cnt&1) sd[i]=false;
}
memset(f,0,sizeof(f));
f[0][0]=1;
for (int i=1;i<=m;i++)
for (int j=0;j<1<<n;j++)
for (int k=0;k<1<<n;k++)
{
if((j&k)==0&&sd[j|k])
f[i][j]+=f[i-1][k];
}
printf("%lld\n",f[m][0]);
}
return 0;
}
结语
祝大家CSP RP++!φ(>ω<*)