比赛 动规 评测结果 AAAAAAAAAA
题目名称 放国王 最终得分 100
用户昵称 TARDIS 运行时间 0.015 s
代码语言 C++ 内存使用 5.34 MiB
提交时间 2017-06-18 21:33:08
显示代码纯文本
#include<bits/stdc++.h>
#define COGS
using namespace std;
const int maxn=15,maxk=1<<10;
long long f[maxn][maxk][maxn*maxn],s[maxk],cnt[maxk],t;
long long n,k,temp;
inline void in(){
	#ifdef COGS
	freopen("placeking.in","r",stdin);
	freopen("placeking.out","w",stdout);
	#endif
	scanf("%d%d",&n,&k);
	temp=(1<<n)-1;
}
inline void dfs(int cur,int ss){
	if (cur==n){
		s[++t]=ss;
		return;
	}
	dfs(cur+1,ss<<1);
	if(!(ss&1)) dfs(cur+1,(ss<<1)+1);
}
inline void init(){
	f[0][0][0]=1;
	for (int i=0;i<=temp;i++){
		cnt[i]=cnt[i>>1]+(i&1);
	}
	for (int i=1;i<=t;i++){
		f[1][i][cnt[s[i]]]=1;
	}
}
inline bool check(int s1,int s2){
	if ((s[s1]&s[s2])||(s[s1]&(s[s2]<<1))||(s[s1]&(s[s2]>>1))) return 0;
	else return 1;
}
inline void dp(){
	for (int i=1;i<=n;i++){
		for (int j=0;j<=k;j++){
			for (int y=1;y<=t;y++){
				for (int q=1;q<=t;q++){
					if (check(y,q)&&j>=cnt[s[y]]){
						f[i][y][j]+=f[i-1][q][j-cnt[s[y]]];
					}
				}
			}
		}
	}
}
inline void deal(){
	dfs(0,0);
	init();
	dp();
}
inline void out(){
	long long ans=0;
	for (int i=0;i<=t;i++){
		ans+=f[n][i][k];
	}
	printf("%lld",ans);
}
int Main(){
	in();
	deal();
	out();
	return 0;
}
int main(){;}
int xlm=Main();