题目链接：https://www.luogu.com.cn/problem/P1896
分析：这道题的n在10以内，又是一个棋盘问题，问k个国王在棋盘中有几种放置方式可以达到互不干涉。最先想到的是dp推导，但是如果用一个二维数组数据会开的太大，容易超时，因此可以想到状态dp
状压dp：即把一系列只有两种选择的情况用0和1来表示，所排列成一个二进制字符串转换为十进制，从而达到压缩的目的。例如一排灯泡开或不开，1为开0为关，一共5个，可把开关状态转换为11011,11000，…等一系列二进制数。
注意：状态压缩一般涉及到位运算，这篇总结的常用的很棒https://blog.csdn.net/u013377068/article/details/81028453
代码如下
```cpp #include<cstdio> #include<iostream> #include<cmath> using namespace std; const double eps=1e-8; const double PI=3.1415926; #define ll long long int n,k; ll f[10][1<<9][82],ans;//f数组表示的就是在总共x行的xx状态下放置xxx个国王一共有几种方式 int c(int st) {//st的二进制表示中存在几个1 int cnt=0; while(st){ if(st%2) cnt++; st/=2; } return cnt; //return __builtin_popcount(st); } bool check1(int st) { //判断单行状态st是否合法 for(int i=0;i+1<n;i++)//判断i和i的上一位 { if((st&(1<<i))&&(st&(1<<(i+1)))) //左移i判断第i位上是否为1，即已经放置了国王 return false; } return true; } bool check2(int st,int st2) {//判断当前行状态st和上一行状态st2是否合法 for(int i=0;i<n;i++) { if(st&(1<<i)){ if(st2&(1<<i)) return false; else if((i+1)<n&&(st2&(1<<(i+1)))) return false; else if(i-1<n&&(st2&(1<<(i-1)))) return false; } } return true; } int main() { cin>>n>>k; for(int i=0;i<n;i++) { for(int st=0;st<(1<<n);st++) { if(!check1(st)) continue; if(i==0) f[i][st][c(st)]=1; else{ for(int j=c(st);j<=k;j++){//控制国王总数不超过k，j表示现在有几个国王 for(int st2=0;st2<(1<<n);st2++){ if(!check1(st2)||!check2(st,st2)) continue; f[i][st][j]+=f[i-1][st2][j-c(st)]; } } } } } for(int st=0;st<(1<<n);st++) ans+=f[n-1][st][k]; cout<<ans<<endl; return 0; }