求条
查看原帖
求条
1159387
jung_le楼主2025/7/18 18:43
#include<bits/stdc++.h>
using namespace std;
long long n,k,dp[15][85][520],sum[520],ans;
bool check(int a,int b){
	if(a&(a<<1)!=0 || b&(b<<1)!=0)return 0;
	if(a&b!=0)return 0;
	if((a<<1)&b!=0)return 0;
	if((b<<1)&a!=0)return 0;
	return 1; 
}
int main(){
	cin>>n>>k;
	sum[0] = 0;
	sum[1] = 1;
	for(int i=2;i<(1<<n);i++){
		if(i%2==0)sum[i] = sum[i>>1];
		else sum[i] = sum[i>>1]+1; 
		cout<<i<<' '<<sum[i]<<'\n';
	}
	dp[0][0][0] = 1; 
	for(int i=1;i<=n;i++){
		for(int s=0;s<(1<<n);s++){
			for(int j=0;j<(1<<n);j++){
				if(check(j,s)){
					for(int w=0;w<=k;w++){
						if(w-sum[s]>=0)dp[i][w][s] +=dp[i-1][w-sum[s]][j];
					}
					
				}
			}
		}
	}
	for(int i=0;i<(1<<n);i++){
		ans+=dp[n][k][i];
	}cout<<ans;
	return 0;
}

2025/7/18 18:43
加载中...