byd人玄关求条橙题
查看原帖
byd人玄关求条橙题
822439
lhz2022楼主2024/10/19 18:54
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() puts("I WILL AK")
#define N 10
#define M 200
int dp[N][1<<N][M];//前i行,状态j,填了k
int can[1<<N];
int sz[1<<N];
int n,m;
int ct=0;
void init(){
	for(int i=0;i<(1<<n);++i){
		sz[i]=__builtin_popcount(i);
		if(!(i&(i<<1))) can[++ct]=i,dp[1][i][sz[i]]=1;
	}
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m;
	init();
	dp[0][0][0]=1;
	for(int i=2;i<=n;++i){
		for(int j=1;j<=ct;++j){
			for(int k=1;k<=ct;++k){
				int x=can[j],y=can[k];
				if((x&y)||(x&(y<<1))||(x&(y>>1))) continue;
				for(int l=0;l<=m;++l) dp[i][x][sz[x]+l]+=dp[i-1][y][l];
			}
		}
	}
	int ans=0;
	for(int i=1;i<=ct;++i){
		ans+=dp[n][i][m];
	}
	cout<<ans;
	return 0;
}
2024/10/19 18:54
加载中...