位运算 限制条件只取决于上一行 用二进制表示 上一行为i 这一行为j
满足
不能有连续的两个1
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
#define int long long
const int N=12,M=1<<10,K=110;
int n,k,f[N][M][K];
vector<int>v,st[M];
bool check(int i){
for(int j=0;j<n-1;j ){
if((i>>j&1)&&(i>>j 1&1))return 0;
}
return 1;
}
int count(int x){
int res=0;
for(int i=0;i<n;i ){
if(x>>i&1)res ;
}
return res;
}
signed main(){
cin>>n>>k;
for(int i=0;i<1<<n;i ){
if(check(i))v.push_back(i);
}
for(int i=0;i<v.size();i ){
for(int j=0;j<v.size();j ){
int x=v[i],y=v[j];
if(((x&y)==0)&&check(x|y))st[x].push_back(y);
}
}
f[0][0][0]=1;
for(int i=1;i<=n 1;i ){
for(int j=0;j<v.size();j ){
for(int ok:st[v[j]]){
int c=count(v[j]);
//cout<<c<<endl;
for(int a=0;a<=k;a ){
if(a>=c)f[i][v[j]][a] =f[i-1][ok][a-c];
}
}
}
}
cout<<f[n 1][0][k]<<endl;
}
