这是一道使用状压dp覆盖图形的问题，我们定义f[i][j][k]表示当第i行的状态为j，前i行一共k个国王时的方案数。其中，j表示将当前这一行状态压缩后对应的二进制数。状态转移方程为f[i][j][k]=∑f[i-1][x][num(x)].我们先预处理出每一个合法的状态，并记录他们用了多少国王，再进行dp即可。
当然，本题可以用滚动数组优化，但是朴素的算法可以通过。
1 #include <iostream> 2 using namespace std; 3 int n,k; 4 typedef long long ll; 5 ll f[11][1<<11][1<<11],ans; 6 int tot,s[1<<11],num[1<<11]; 7 inline int get(int s) { 8 int ret=0; 9 while(s) { 10 ret++; 11 s&=s-1; 12 } 13 return ret; 14 } 15 int main() { 16 ios::sync_with_stdio(false); 17 cin>>n>>k; 18 for(int i=0;i<1<<n;i++) { 19 if(i&(i<<1)) continue ; 20 s[++tot]=i; 21 num[tot]=get(i); 22 } 23 f[0][1][0]=1; 24 for(int i=1;i<=n;i++) { 25 for(int j=1;j<=tot;j++) 26 for(int x=num[j];x<=k;x++) 27 for(int k=1;k<=tot;k++) 28 if(!(s[j]&s[k])&&!(s[k]&(s[j]<<1))&&!(s[k]&(s[j]>>1))) 29 f[i][j][x]+=f[i-1][k][x-num[j]]; 30 } 31 for(int i=1;i<=tot;i++) 32 ans+=f[n][i][k]; 33 cout<<ans<<endl; 34 return 0; 35 }
原文：https://www.cnblogs.com/shl-blog/p/10702456.html
