传送门:https://www.lydsy.com/JudgeOnline/problem.php?id=1087
题意:每个点的八周不能放点，问放k个点一共有多少种方案
题解:n特别小，所以可以想到状态压缩，因为在棋盘上面，所以根据经验应该是从上往下递推的，因为状态数比较多，我们先预处理一下整个棋盘
于是：我们目前拥有的状态数是：有n行棋盘，有k个点，每一行和下一行的状态是相互相关的
设dp[i][j][k]表示前i行放j个点时第i行的状态为k，那么我们最终的答案就是∑dp[n][k][i] i->[0,1<<n]
代码如下：
#include <map> #include <set> #include <cmath> #include <ctime> #include <stack> #include <queue> #include <cstdio> #include <cctype> #include <bitset> #include <string> #include <vector> #include <cstring> #include <iostream> #include <algorithm> #include <functional> #define fuck(x) cout<<"["<<x<<"]"; #define FIN freopen("input.txt","r",stdin); #define FOUT freopen("output.txt","w+",stdout); //#pragma comment(linker, "/STACK:102400000,102400000") using namespace std; typedef long long LL; typedef pair<int, int> PII; const int maxn = 1e5+5; const int INF = 0x3f3f3f3f; const int MOD = 1e9+7; int n,k,num[1000]; LL dp[10][1000][1000]; bool flag[1000]; LL ans; /*dp[i][j][k]为前i行已经放了j个国王并且第i行的状态为k（二进制）的方案数， 那么dp[i][j][k] = Σdp[i-1][j - num[k]][p], 其中num数组记录着一行为状态k的放的国王的数目，p为上一行符合要求的状态*/ void init(){ for(int i=0;i<(1<<n);i++){ //num:第i行可以放的数目 if(!(i&(i<<1))){ cout<<i<<" "<<(i<<1)<<" "<<(i&(i<<1))<<endl; flag[i]=1; int t=i; while(t){ num[i]+=(t&1); t>>=1; } //当前状态i放数量num【i】的方法 dp[1][num[i]][i]=1; } } } int main(){ #ifndef ONLINE_JUDGE FIN #endif scanf("%d%d",&n,&k); init(); for(int i=2;i<=n;i++){//控制行数 for(int j=0;j<=k;j++){//控制国王的个数 for(int now=0;now<(1<<n);now++){//控制当前状态 if(!flag[now]) continue; if(num[now]>j) continue; for(int last=0;last<(1<<n);last++){//控制上一个状态 if(!flag[last]) continue; //如果存在攻击范围重叠的情况的话 跳过 if((last&now)||((now<<1)&last)||(now>>1)&last) continue; // dp[i][j][now]+=dp[i-1][j-num[now]][last]; } } } } for(int i=0;i<(1<<n);i++){ ans+=dp[n][k][i]; } printf("%lld ",ans); }