比赛 状态压缩DP练习 评测结果 AAAAAAAAAA
题目名称 放国王 最终得分 100
用户昵称 梦那边的美好ET 运行时间 0.226 s
代码语言 C++ 内存使用 22.25 MiB
提交时间 2019-05-28 19:39:13
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,k,f[11][1<<10][100],sum;
int ju(int x,int y){
	sum=0;
	for(int i=1;i<=n;i++){
		if(x>>(i-1)&1){sum++;
			if((y>>(i-1))&1)return 0;
			if((y>>(i))&1)return 0;	
			if((y>>(i-2))&1)return 0;
			if((x>>(i-2))&1)return 0;
			if((x>>(i))&1)return 0;				
		}
	}
	return 1;
}
int main(){
	freopen("placeking.in","r",stdin);
	freopen("placeking.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	f[0][0][0]=1;
	for(int a=1;a<=n;a++)
		for(int i=0;i<=(1<<n)-1;i++)
			for(int j=0;j<=(1<<n)-1;j++)
				if(ju(i,j))
					for(int p=0;p<=k-sum;p++)
						f[a][i][p+sum]+=f[a-1][j][p];
	sum=0;
	for(int i=0;i<=(1<<n)-1;i++)sum+=f[n][i][k];
	printf("%lld",sum);
	return 0;
}