题目大意
求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。
1≤N,M≤11
思路：
一：
用f[i][s]表示第i行状态为s的方案数；
对于s 0表示i-1列无伸向第i列的方格，1表示有伸向第i列的方格；
先预处理可用状态（对这一题所有状态都可用）
点击查看代码
state.clear();
for(int i=0;i< 1<<n;i++)
{
state.push_back(i);
}
二：
找可转移的状态 即 对于状态 a ,b 满足(a&b)==0&&check(a|b)
点击查看代码
bool check(int state)
{
int res=0;
bool flag=true;
for(int i=0;i<n;i++)
{
if(state>>i &1)
{
if(res&1){
flag=false;
break;
}
res=0;
}
else res++;
}
if(res&1) flag=false;
return flag;
}
//main()里
for(int i=0;i<state.size();i++)
{
head[i].clear();
for(int j=0;j<state.size();j++)
{
int a=state[i],b=state[j];
if((a&b) ==0&& check(a|b) )
head[i].push_back(j);
}
}
三：
状态计算：
点击查看代码
memset(f,0,sizeof(f ));
f[0][0]=1;
for(int i=1;i<=m;i++)
{
for(int a=0;a<state.size();a++)
{
for(int b:head[a])
{
f[i][a]+=f[i-1][b];
}
}
}
cout<<f[m][0]<<endl;
全部代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=13;
const int M=1<<11;
vector<int> state;
vector<int> head[M];
long long f[N][M];
int n,m;
bool check(int state)
{
int res=0;
bool flag=true;
for(int i=0;i<n;i++)
{
if(state>>i &1)
{
if(res&1){
flag=false;
break;
}
res=0;
}
else res++;
}
if(res&1) flag=false;
return flag;
}
int main()
{
while(cin>>n>>m,n||m)
{
state.clear();
for(int i=0;i< 1<<n;i++)
{
state.push_back(i);
}
for(int i=0;i<state.size();i++)
{
head[i].clear();
for(int j=0;j<state.size();j++)
{
int a=state[i],b=state[j];
if((a&b) ==0&& check(a|b) )
head[i].push_back(j);
}
}
memset(f,0,sizeof(f ));
f[0][0]=1;
for(int i=1;i<=m;i++)
{
for(int a=0;a<state.size();a++)
{
for(int b:head[a])
{
f[i][a]+=f[i-1][b];
}
}
}
cout<<f[m][0]<<endl;
}
return 0;
}