题目大意：
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案
国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子
思路：
状压dp
三维分别是当前填了几行 填的最后一行的状态 填了几个国王
方程很好想
但是需要预处理一下那些状态合法 以及两个状态之间是否可以相邻
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstdlib> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<queue> 9 #define inf 2139062143 10 #define ll long long 11 #define MAXN 10 12 using namespace std; 13 inline int read() 14 { 15 int x=0,f=1;char ch=getchar(); 16 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 17 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 18 return x*f; 19 } 20 int n,m,t,k[MAXN*60],cnt,num[MAXN*60]; 21 ll dp[MAXN][MAXN*60][MAXN*MAXN]; 22 bool ok[MAXN*60][MAXN*60]; 23 void dfs(int pos,int f,int fst) 24 { 25 k[++cnt]=pos,num[cnt]=f; 26 for(int i=fst+2;i<=n;i++) dfs(pos+(1<<(i-1)),f+1,i); 27 } 28 int main() 29 { 30 n=read(),m=read(); 31 dfs(0,0,-1); 32 for(int i=1;i<=cnt;i++) 33 for(int j=i;j<=cnt;j++) 34 ok[i][j]=ok[j][i]=((k[i]&k[j])||((k[i]<<1)&k[j])||((k[j]<<1)&k[i]))?0:1; 35 for(int i=1;i<=cnt;i++) dp[1][i][num[i]]=1LL; 36 for(int g=2;g<=n;g++) 37 for(int i=1;i<=cnt;i++) 38 for(int d=num[i];d<=m;d++) 39 for(int j=1;j<=cnt;j++) 40 if(ok[i][j]) dp[g][i][d]+=dp[g-1][j][d-num[i]]; 41 ll ans=0; 42 for(int i=1;i<=cnt;i++) ans+=dp[n][i][m]; 43 printf("%lld",ans); 44 }