状压dp模板题：
dp[i][j][k]为到了第i行，第i行的状态，一共有多少的国王。
预处理出第i行的所有可行的状态，显然不能有国王相邻，也不能有超过k个国王的可能
dp转移：
显然dp[ i ][ x ][ k ]是上一行情况累加过来：
dp[i][x][k]+=dp[i-1][y][k-popcount(x)]
最后统计出所有dp[n][x][m]的情况即可
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define popb pop_back #define fi first #define se second const int N=15; //const int M=; //const int inf=0x3f3f3f3f; //const ll INF=0x3ffffffffffff; int T,n,m; ll dp[N][1<<N][N]; vector< pair<int,int> > v; // first状态，second状态的个数 inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); n=read(),m=read(); for(int i=0;i<(1<<n);i++) { if(i&(i<<1)) continue; if(__builtin_popcount(i)<=m) v.pb(mp(i,__builtin_popcount(i))); } for(auto x:v) dp[1][x.fi][x.se]=1; for(int i=2;i<=n;i++) for(auto x:v) for(auto y:v) for(int k=y.se;k<=m;k++) { if(x.fi&y.fi) continue; if((x.fi<<1)&y.fi) continue; if(x.fi&(y.fi<<1)) continue; dp[i][x.fi][k]+=dp[i-1][y.fi][k-x.se]; } ll ans=0; for(auto x:v) ans+=dp[n][x.fi][m]; printf("%lld",ans); return 0; }