求助!
查看原帖
求助!
241494
yrqtql楼主2020/9/10 20:31
#include<bits/stdc++.h>
using namespace std;
inline int lowbit(const int &x)
{
	return x&(-x);
}
int Get(int x)
{
	int cnt=0;
	while(x){
		++cnt;
		x^=lowbit(x);
	}
	return cnt;
}
int n,k,sum[502];
long long ans,f[101][502][101];//f[i][j][k]表示到第i行为止状态为j时放下k个国王的方案数
int main()
{
	scanf("%d%d",&n,&k);
	for(register int i=0;i<(1<<n);++i)
		sum[i]=Get(i);
	for(register int i=0;i<(1<<n);++i)
		if(!(i&(i<<1))&&sum[i]<=k)
			f[1][i][sum[i]]=1;
	for(register int i=2;i<=n;++i)
		for(register int j=0;j<(1<<n);++j){
			if(j&(j<<1))
				continue;
			for(register int l=0;l<(1<<n);++l){
				if(l&(1<<l)||l&j||(l<<1)&j||(j<<1)&l)
					continue;
				for(register int t=1;t<=k-sum[j];++t)
					f[i][j][sum[j]+t]+=f[i-1][l][t];
			}
		}
	for(register int i=1;i<=n;++i)
		for(register int j=0;j<(1<<n);++j)
			if(!(j&(1<<j)))
				ans+=f[i][j][k];
	printf("%lld\n",ans);
	return 0;
}
2020/9/10 20:31
加载中...