题目链接：https://www.luogu.org/problem/P1896
题意：给你一个n*n的棋盘，摆上k个国王，要求每个国王九宫格范围内没有别的国王
分析：状压DP入门经典题
我们可以用二进制数串表示状态比如1010 就是该行第二个第四个有国王，第一三个就没有
判断九宫格范围内是否有别的国王，我们从上到下依次递推
对于当前行，就是i&(i<<1)不为0的话，就说明相邻的有
要特别注意s的起点，如果不能理解就直接记住从0开始的做法就好
具体的讲解在代码里面
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int maxn=1e3+7; const int N=1e4; int n,k; int state[1500],king[1500];//分别表示当前状态，以及当前状态的国王数 ll dp[15][1500][100];//dp[i][j][k]表示第i行，状态j，总共用了k个国王的方案数 ll res,ans; void init(){ int tot=1<<n;//左移n位，遍历的时候记住遍历到tot-1，比如5个数位我们用64来表示，63即11111 for(int i=0;i<tot;i++){ if(i&(i<<1))continue;//有值说明当前行不满足左右不相邻 state[++res]=i; int temp=i; while(temp){ if(temp%2)king[res]++; temp>>=1; } } } int main(){ scanf("%d%d",&n,&k); init();//初始化，求出满足本行内不相邻的情况（状态） for(int i=1;i<=res;i++){//初始化第一行 if(king[i]<=k)dp[1][i][king[i]]=1; } for(int i=2;i<=n;i++)//从第二行开始一行行的找 for(int j=1;j<=res;j++){//枚举当前行状态 for(int p=1;p<=res;p++){//枚举上一行的状态 //因为要求一个国王九宫格内不允许有另外的国王，具体到上一行就是上一行的正上，左上，右上都不能有国王（也就是状态数不能有1） //故记下来三个操作分别是排除正上，左上，右上有国王的情况(注意只能左移，右移会损失精度) if(state[j]&state[p])continue; if(state[j]&(state[p]<<1))continue; if((state[j]<<1)&state[p])continue; for(int s=0;s<=k;s++){//枚举当前行之前已经用了多少个国王了 //注：这里s的取值非常非常重要！！！！直接影响到dp数组的意义 //如果s的取值从0开始，那表示的是这一行和之前一起放king[j]+s个国王的方案数 //如果从1开始，表示的是到了这一行正好放king[j]+s个国王，以前够了king[j]+s个棋子的方案没有记录在内 if(s+king[j]<=k) dp[i][j][king[j]+s]+=dp[i-1][p][s]; } } } //如果前面s取值从1开始，还要枚举行数i从1到n for(int i=1;i<=res;i++){//记录答案 ans+=dp[n][i][k]; } //printf("%I64d",ans); cout<<ans; return 0; }