比赛 状态压缩DP练习 评测结果 AAAAAAAAAA
题目名称 放国王 最终得分 100
用户昵称 Hale 运行时间 0.017 s
代码语言 C++ 内存使用 122.50 MiB
提交时间 2019-05-28 19:48:02
显示代码纯文本
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=7e6+7;
LL tot,ans,cnt,n,k,sum;
LL state[N],f[11][200][121],king[N];
void init()
{
	tot=(1<<n)-1;
	for (int i=0;i<=tot;i++)
	{
		if (!((i<<1)&i))
		{
			state[++cnt]=i;
			int t=i;
			while(t)
			{
				king[cnt]+=t%2;
				t>>=1;	
			}
		}
	}
}
int main()
{
	freopen("placeking.in","r",stdin);
	freopen("placeking.out","w",stdout);
	scanf("%lld%lld",&n,&sum);
	init();
	for (int i=1;i<=cnt;i++)
	if (king[i]<=sum) f[1][i][king[i]]=1;
	for (int i=2;i<=n;i++)
	 for (int j=1;j<=cnt;j++)
	  for (int p=1;p<=cnt;p++)
	{
		if (state[j]&(state[p])) continue;
		if (state[j]&(state[p]<<1)) continue;
		if ((state[j]<<1)&state[p]) continue;
		for (int k=1;k<=sum;k++)
		{
			if (king[j]+k>sum) continue;
			f[i][j][king[j]+k]+=f[i-1][p][k];
		} 
	}
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=cnt;j++)
	 ans+=f[i][j][sum];
	printf("%lld",ans);
	return 0;
}