题意：给一个n*n的格子，放入k个物体，要求每个物体的相邻8个方向都不能放物体，问方案数。
题解：dp[i][j][k]表示前i行放了j个物体，且第i行状态为k的方案数，转移为dp[i][j][k]=∑dp[i-1][j-num[p]][p]，num[p]表示单行状态为p能放几个物体，可以先预处理出来，另外判断相邻两行是否符合也有个很简单的技巧，具体见代码。
代码：
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; int n, k; ll dp[11][110][(1<<10)+10]; int num[(1<<10)+10]; bool flag[(1<<10)+10]; void init(){ memset(num, 0, sizeof(num)); memset(flag, false, sizeof(flag)); for(int i = 0; i<=(1<<10); i++){ if(!(i&(i<<1))){ flag[i] = true; int ans = 0; int x = i; while(x){ if(x&1){ ans++; } x>>=1; } num[i] = ans; dp[1][num[i]][i] = 1; } } } int main(){ init(); scanf("%d %d", &n, &k); for(int i = 2; i<=n; i++){ for(int j = 0; j<=k; j++){ for(int now = 0; now<=(1<<n)-1; now++){ if(flag[now] == false){ continue; } if(num[now]>j){ continue; } for(int p = 0; p<=(1<<n)-1; p++){ if(flag[p] == false){ continue; } if((now&p) || ((now<<1)&p) || ((now>>1)&p)){ continue; } dp[i][j][now]+=dp[i-1][j-num[now]][p]; } } } } ll res = 0; for(int i = 0; i<=(1<<n)-1; i++){ res+=dp[n][k][i]; } cout<<res<<endl; return 0; }
原文：https://www.cnblogs.com/grimcake/p/9949790.html