$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$
思路:
1. 先考虑横着的再考虑竖着的,横着的合法方案数就是总方案数
2. f[i][j] 表示前 i-1 列已排好,从第 i-1 列到第 i 列的竖着的状态是 j 的方案数
3. f[i][j] 和 f[i-1][k],状态 j 和状态 k 两者不能有交集,且必须合法(即第 i-1 列剩下连续格子是偶数)
4. 先预处理所有的合法状态
5. 再预处理对于状态 j 有哪些状态 k 可以与之匹配
6. 状态转移方程:f[i][j] += f[i-1][k]
完整代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
int n,m;
LL f[N][M];
bool st[M];
vector<int> state[M];
int main()
{
while(cin>>n>>m,n||m)
{
//1. 预处理出哪些状态是合法状态
for(int i=0;i<1<<n;i++)
{
int cnt=0;
bool is_valid=true;
for(int j=0;j<n;j++)
if(i>>j&1)
{
if(cnt&1)
{
is_valid=false;
break;
}
cnt=0;
}
else cnt++;
if(cnt&1) is_valid=false;
st[i]=is_valid;
}
//2. 预处理出对于状态 j 可以有哪些状态 k 可以与之匹配
for(int j=0;j<1<<n;j++)
{
state[j].clear();
for(int k=0;k<1<<n;k++)
if((j&k)==0&&st[j|k])
state[j].push_back(k);
}
//3. dp 部分
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(auto k:state[j])
f[i][j]+=f[i-1][k];
cout<<f[m][0]<<endl;
}
return 0;
}