求调
查看原帖
求调
686279
codeLYX楼主2023/12/28 16:51
#include<bits/stdc++.h>
using namespace std;
#define bit_max 9
#define int long long
inline bitset<bit_max> get(int x){
	bitset<bit_max> tmp(x);
	return tmp;
}
bool check(bitset<bit_max> a){
	for(int i=1;i<bit_max;i++){
		if(a[i]&&a[i-1]){
			return 0;
		}
	}
	return 1;
}
signed main(){
	int n,K;
	cin>>n>>K;
	int mmax=pow(2,n);
	int dp[n+1][mmax][K+1];
	memset(dp,0,sizeof(dp));
	for(int i=0;i<mmax;i++){
		if(check(get(i))){
			dp[1][i][get(i).count()]=1;
			//cout<<get(i)<<" "<<dp[1][i][get(i).count()]<<"\n";
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=0;j<mmax;j++){
			if(!check(get(j)))
				continue;
			for(int k=0;k<mmax;k++){
				if((j&(k<<1))||(j&k)||(j&(k>>1))){
					continue;
				}
				for(int l=get(j).count();l<=K;l++){
					dp[i][j][l]+=dp[i-1][k][l-get(j).count()];
					//cout<<i<<" "<<get(j)<<" "<<l<<" "<<get(k)<<" "<<l-get(j).count()<<" "<<dp[i-1][k][l-get(j).count()]<<" "<<dp[i][j][l]<<"\n";
				}
			}
		}
	}
	int answer=0;
	for(int i=0;i<mmax;i++){
		answer+=dp[n][i][K];
	}
	cout<<answer;
}
2023/12/28 16:51
加载中...