1 #include<cstdio> 2 #include<iostream> 3 #define M 600 4 int b1[M],b2[M][M],n,m,s,sum[M]; 5 long long f[10][M][M],ans; 6 using namespace std; 7 int main() 8 { 9 scanf("%d%d",&n,&m); 10 s=(1<<n)-1; 11 int i=2; 12 for(int i=0;i<=s;i++) 13 if((i&(i>>1))==0) 14 { 15 int q=0; 16 b1[i]=1; 17 for(int j=i;j;j=j>>1) 18 if(j&1) 19 q++; 20 sum[i]=q; 21 } 22 for(int i=0;i<=s;i++) 23 if(b1[i]) 24 for(int j=0;j<=s;j++) 25 if(b1[j]&&(i&j)==0&&((i>>1)&j)==0&&((i<<1)&j)==0) 26 b2[i][j]=1; 27 for(int i=0;i<=s;i++) 28 f[1][sum[i]][i]=1; 29 for(int i=1;i<n;i++) 30 for(int j=0;j<=s;j++) 31 if(b1[j]) 32 for(int k=0;k<=s;k++) 33 if(b1[k]&&b2[j][k]) 34 for(int q=sum[j];q+sum[k]<=m;q++) 35 f[i+1][q+sum[k]][k]+=f[i][q][j]; 36 for(int i=0;i<=s;i++) 37 ans+=f[n][m][i]; 38 printf("%lld ",ans); 39 return 0; 40 }
n<=9，状压dp，用01字符串表示有无国王，所以每行一共有2^n-1种可能，先按左右处理出这些可能，再按上下处理各种可能情况能否作上下关系。