这是一道状压dp的入门练习题
我们可以预处理出每一行国王的合法摆放方案，然后进行dp。
我们定义f[i][j][k]表示前i行，第i行的状态为j且使用了k个国王的合法方案数，那么存在
f[i][j][k]=∑f[i-1][j'][k'],其中j&j'=0,j&j'<<1=0,j&j'>>1=0
注意一点，本题没有规定k个国王必须放满n行，所以在任何情况下都可以结束dp。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 int n,k; 8 long long f[10][1<<10][90],ans; 9 inline int read() { 10 int ret=0; 11 int op=1; 12 char c=getchar(); 13 while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();} 14 while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); 15 return ret*op; 16 } 17 int a[2010],sum[2010],num; 18 inline int lowbit(int i) { 19 return (-i)&i; 20 } 21 int main() { 22 n=read(); k=read(); 23 for(int i=0;i<1<<n;i++) { 24 if(i&(i<<1)) continue ; 25 a[++num]=i; 26 int now=i; 27 while(now) { 28 sum[num]++; 29 now-=lowbit(now); 30 } 31 } 32 for(int i=1;i<=num;i++) 33 if(sum[i]<=k) f[1][a[i]][sum[i]]=1; 34 for(int i=2;i<=n;i++) { 35 // memset(f[i&1],0,sizeof(f[i&1])); 36 for(int j=1;j<=num;j++) 37 for(int l=1;l<=num;l++) 38 if((a[j]&a[l])==0&&(a[j]&(a[l]<<1))==0&&(a[l]&(a[j]<<1))==0) 39 for(int x=1;x<=k;x++) { 40 if(x+sum[j]<=k) 41 f[i][a[j]][x+sum[j]]+=f[i-1][a[l]][x]; 42 // else break; 43 } 44 } 45 for(int i=1;i<=n;i++) 46 for(int j=1;j<=num;j++) 47 ans+=f[i][a[j]][k]; 48 printf("%lld ",ans); 49 return 0; 50 }