题目链接：https://www.luogu.com.cn/problem/P1896
状压DP，一般都是枚举行，然后枚举每一行的状态（二进制），每一行的最大状态也就是1<<(len)-1，然后重点便是一些二进制的操作。
本题将每一行的方案二进制压成一维。然后只需二进制判断同一行中左右是否冲突，与上一行是否冲突，注意判断是否冲突的二进制方法。
在dp[][][]中，第一维表示行数，第二维表示当前行的状态，第三维表示到当前为止用了多少个国王。然后暴力转移即可。
AC代码：
1 #include<cstdio> 2 using namespace std; 3 typedef long long ll; 4 const int N=1000+10; 5 ll dp[10][N][100];//行 状态 限定 6 int state[N]; 7 int cul(int x){ 8 int ans=0; 9 while(x){ 10 if(x&1) ans++; 11 x>>=1; 12 } 13 return ans; 14 } 15 int judge(int x,int y){ 16 if(x&y) return 0; 17 if(x&(y>>1)) return 0; 18 if(x&(y<<1)) return 0; 19 return 1; 20 } 21 int main(){ 22 int n,m; 23 scanf("%d%d",&n,&m); 24 int maxstate=(1<<n); 25 for(int i=0;i<maxstate;i++) state[i]=((i&(i<<1))==0&&(i&(i>>1))==0);//判断一行中每一个状态左右是否满足 26 for(int j=0;j<maxstate;j++) if(state[j]&&cul(j)<=m) dp[1][j][cul(j)]=1;//处理第一行 27 for(int i=2;i<=n;i++){ 28 for(int j=0;j<maxstate;j++){//当前一行的状态 29 if(state[j]==0) continue; 30 for(int k=0;k<maxstate;k++){//上一行的状态 31 if(state[k]==0||judge(j,k)==0) continue; 32 for(int l=m;l>=cul(j);l--) dp[i][j][l]+=dp[i-1][k][l-cul(j)];//l枚举当前总共使用过的国王 33 } 34 } 35 } 36 ll ans=0; 37 for(int i=0;i<maxstate;i++) ans+=dp[n][i][m];//显然 38 printf("%lld\n",ans); 39 return 0; 40 }
原文：https://www.cnblogs.com/New-ljx/p/12493312.html
