对于这类棋盘问题 要关注的是这一行与前一行的关系
设dp[i][j][state]表示前i行，已经放了j个国王，状态为state的方案数
然后枚举i，枚举j，再枚举state，再枚举上一行last
先判断state,last各自是否合法，再判断他们俩合起来会不会冲突
最后答案就是最后一行所有状态的方案数之和
我这个写法好像常数巨大啊。。。
#include<bits/stdc++.h> #define N 10 #define STATE 520 #define ll long long using namespace std; int n,k; ll dp[N][N*N][STATE]; inline bool ok(int state)//判断状态是否合法 { for(int i=1;i<n;i++) //跳过第1位 { if(state&(1<<i)) //当前这位是1 { if(state&(1<<(i-1))||state&(1<<(i+1))) return false; } } return true; } inline int popcnt(int x)//二进制下有多少个1 { int cnt=0; while(x) { if(x&1) cnt++; x>>=1; } return cnt; } inline bool conflict(int s1,int s2) { if((s1&s2)||(s1&(s2<<1))||(s1&(s2>>1))) return true; return false; } int main() { scanf("%d%d",&n,&k); const int max_state=1<<n; for(int state=0;state<max_state;state++) if(ok(state)) dp[1][popcnt(state)][state]=1; for(int i=2;i<=n;i++) { for(int j=0;j<=k;j++) { for(int state=0;state<max_state;state++) { if(!ok(state)) continue; if(popcnt(state)>j) continue; for(int last=0;last<max_state;last++) { if(conflict(state,last)) continue; dp[i][j][state]+=dp[i-1][j-popcnt(state)][last]; } } } } ll ans=0; for(int i=0;i<max_state;i++) ans+=dp[n][k][i]; cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9853034.html
