传送门
虽然水题一道但是还是调了很长时间，最近做题状态很差啊，很迷。。
状压dp，比较简单没什么优化，把每一行作状态记录，所以跑了32ms（orz 0ms大神），设f[i][j][k]表示第i行状态为j用了k个皇的方案数，然后有一个很弱智的优化，把可行的状态处理出来，这里的可行是指上下行不斥每一行中的方格彼此不斥的状态。然后就有f[i][j][k]=f[i-1][l][k-cnt[j]]（cnt[i]表示状态i的国王个数）。
注意：long long
代码：
#include<iostream> #include<stdio.h> #include<math.h> #define ll long long using namespace std; const int Maxn=600; int p[Maxn],m[Maxn][Maxn],cnt[Maxn]; ll f[20][Maxn][Maxn]; int main() { int n,k,tmp=0,x; ll ans=0; scanf("%d%d",&n,&k); x=pow(2,n)-1; for(int i=0;i<=x;i++) if((i&(i<<1))==0) { int s=0; for(int j=i;j;j>>=1) s+=(j&1); if(s<=k) { p[++tmp]=i; cnt[tmp]=s; } } for(int i=1;i<=tmp;i++) for(int j=1;j<=tmp;j++) m[i][j]=m[j][i]=((p[i]>>1)&p[j])||(p[i]&p[j])||((p[j]>>1)&p[i])?0:1; for(int i=1;i<=tmp;i++) f[1][i][cnt[i]]=1; for(int i=2;i<=n;i++) for(int j=1;j<=tmp;j++) for(int s=1;s<=tmp;s++) if(m[j][s]==1) for(int l=cnt[s];l<=k;l++) f[i][s][l]+=f[i-1][j][l-cnt[s]]; for(int i=1;i<=tmp;i++) ans+=f[n][i][k]; printf("%lld",ans); return 0; }