https://blog.csdn.net/tenkuo/article/details/154955926

E25 状态压缩DP 小国王

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int slen,s[1<<10];//s[i]表示第i个 行合法状态
int sk[1<<10];//sk[i]表示第i个 行合法状态 有多少个1 
LL f[11][101][1<<10];//第 1 ~ i 行总共放k个国王、且第i行的 行合法状态 是 v 时的合法放置方案数量

int main()
{
    int n,K;scanf("%d%d",&n,&K);
   
    slen=0;
    for(int v=0;v<(1<<n);v++) if((v&(v>>1))==0&&(v&(v<<1))==0)s[++slen]=v;//保存合法状态 

    memset(sk,0,sizeof(sk));
	memset(f,0,sizeof(f));
	for(int i=1;i<=slen;i++)
	{
		for(int j=0;j<n;j++)if(s[i]&(1<<j))sk[i]++;
		f[1][sk[i]][s[i]]=1;
	}
	 
    for(int i=2;i<=n;i++)for(int ki=0;ki<=K;ki++)for(int j=1;j<=slen;j++)//if(ki>=sk[j])
    {
    	for(int jj=1;jj<=slen;jj++)//if(ki-sk[j]>=sk[jj])
			if(((s[j] & (s[jj]>>1))==0) &&((s[j] & (s[jj]<<1))==0) &&((s[j]&s[jj])==0))
				f[i][ki][s[j]]+=f[i-1][ki-sk[j]][s[jj]];
    }
    LL ans=0;for(int i=1;i<=slen;i++)ans+=f[n][K][s[i]];
    printf("%lld\n",ans);
    return 0;
}