比赛 动规 评测结果 AAAAAAAAAA
题目名称 放国王 最终得分 100
用户昵称 swttc 运行时间 0.068 s
代码语言 C++ 内存使用 61.36 MiB
提交时间 2017-06-18 21:33:51
显示代码纯文本
#include<iostream>
#include<cstdio>

int t,s[2000],n,k,cnt[2000];
long long f[20][2000][200];

void dfs(int cur,int ss)
{
	if(cur==n)
	{
		s[++t]=ss;//s[i]第i个状态 
		return;
	}
	dfs(cur+1,ss<<1);//不管下一位能否放王,都搜不放的情况 
	if(!(ss&1)) dfs(cur+1,(ss<<1)+1);//下一位不能放 
}

void _init()
{
	f[0][0][0]=1;
	for(int i=1;i<=(1<<n)-1;i++)//1<<n为多了一位的状态,减一后变为全是一的满状态 
	{
		cnt[i]=cnt[i>>1]+(i&1);//cnt[i]为i状态王的个数 
	}
	for(int i=1;i<=t;i++)
	 f[1][i][cnt[s[i]]]=1;
} 

int 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;
}

int main()
{
	freopen("placeking.in","r",stdin);
	freopen("placeking.out","w",stdout);
	scanf("%d%d",&n,&k);
	dfs(0,0); 
	_init();
	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[q]])
			   {
			   	f[i][q][j]+=f[i-1][y][j-cnt[s[q]]];
				} 
	   }
	long long  ans=0;
	for(int i=0;i<=t;i++)
	 ans+=f[n][i][k]; 
	printf("%lld",ans);
	return 0;
}