欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1087
题意概括
在n*n的棋盘上面放k个国王，使得他们互相无法攻击，问有多少种摆法。
题解
dp[i][j][x]表示前i行，状态为j，总共放了x个国王的方案总数。
然后简单的转移一下即可。
当然这样要炸。
只需要在这之前把每行的合法情况筛选一下即可，这样的情况总数不到100。
然后就可以了。
代码
#include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> using namespace std; typedef long long LL; const int S=(1<<9)+5; int n,k; int sit[S],bitsum[S],sz; LL dp[11][S][100]; int cnt1(int x){ int ans=0; while (x){ ans+=x&1; x>>=1; } return ans; } int main(){ scanf("%d%d",&n,&k); sz=0; for (int i=0;i<(1<<n);i++) if (!(i&(i<<1))) sit[++sz]=i,bitsum[sz]=cnt1(i); memset(dp,0,sizeof dp); dp[0][1][0]=1; for (int i=0;i<n;i++) for (int j=1;j<=sz;j++) for (int x=0;x<=k;x++){ if (!dp[i][j][x]) continue; for (int y=1;y<=sz;y++) if (!(sit[j]&sit[y])&&!(sit[j]&(sit[y]<<1))&&!((sit[j]<<1)&sit[y])&&x+bitsum[y]<=k) dp[i+1][y][x+bitsum[y]]+=dp[i][j][x]; } LL ans=0; for (int i=1;i<=sz;i++) ans+=dp[n][i][k]; printf("%lld",ans); return 0; }