这道题看上去很像八皇后，但是变成的国王以后无疑会增加很多情况，暴力会炸。而因为国王只影响到上下左右八个各自，所以我们能用状压DP解决。
设f[i][j][k]表示第i行，第j种状态下，一共有k个国王的情况。其中j是一个二进制数，比如74代表的是它的二进制1001010代表的是这一行的国王摆放情况。
然后预处理num[i]代表i这种状态需要的国王数，比如num[74]=3
转移方程就是：f[i][j][k]+=f[i-1][t][k-num[j]];其中k、t分别表示当前行的状态和上一行的状态。其中保重k、t互相满足。
代码如下：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <vector> using namespace std; #define MAXN 155 #define INF 10000009 #define MOD 10000007 #define LL long long #define in(a) a=read() #define REP(i,k,n) for(int i=k;i<=n;i++) #define DREP(i,k,n) for(int i=k;i>=n;i--) #define cl(a) memset(a,0,sizeof(a)) inline int read(){ int x=0,f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void out(int x){ if(x<0) putchar('-'),x=-x; if(x>9) out(x/10); putchar(x%10+'0'); } LL n,m,total,f[11][MAXN][MAXN],num[MAXN],s[MAXN],ans; int main(){ in(n);in(m); REP(i,0,(1<<n)-1){ if(i&(i<<1)) continue; int k=0; REP(j,0,n-1) if(i&(1<<j)) k++; s[++total]=i; num[total]=k; } f[0][1][0]=1; REP(i,1,n) REP(j,1,total) REP(k,0,m) if(k>=num[j]) REP(t,1,total) if(!(s[t]&s[j]) && !(s[t]&(s[j]<<1)) && !(s[t]&(s[j]>>1))) f[i][j][k]+=f[i-1][t][k-num[j]]; REP(i,1,total) ans+=f[n][i][m]; cout<<ans; return 0; }
转载于:https://www.cnblogs.com/jason2003/p/9636512.html
相关资源：JAVA上百实例源码以及开源项目