【数据删除】被收了，原因：大义灭亲
开状压了
但是讲解视频的模糊程度和二十年前的电视剧不相上下
\(B\) 互不侵犯
状压模板
状态转移方程为 $dp_{i,j,k}=\sum\limits_{x=1}^{cnt} dp_{i-1,x,k-sta_j} $，其中 (sit[j]&sit_[x]==0)&&((sit[j]<<1)&sit[x]==0)&&(sit_[j]&(sit[x]}<<1)==0)。
\(i\) 表示 填补的第 \(i\) 层，\(j\) 表示 第 \(i\) 层填的 \(j\) 种合法情况，\(k\) 表示到第 \(i\) 层一共填了 \(k\) 个国王，\(sta_i\) 表示 第 \(i\) 种合法情况 填了 \(sta_i\) 个国王
，\(sit_{i}\) 表示 第 \(i\) 种合法情况 的 填补情况
先预处理出每一行合法的情况
然后枚举，判断是否合法就行了
点击查看代码
#include <bits/stdc++.h>
using namespace std;
long long ans;
long long sta[2005], sit[2005], dp[15][2005][105];
int n, k, cnt;
void dfs(int x,int w,int num){
if(x>=n){
sit[++cnt]=w;
sta[cnt]=num;
return ;
}
dfs(x+1,w,num);
dfs(x+2,w+(1<<x),num+1);
}
// void dfs(int x, int num, int cur) {
// if (cur >= n) { // 有新的合法状态
// sit[++cnt] = x;
// sta[cnt] = num;
// return;
// }
// dfs(x, num, cur + 1); // cur位置不放国王
// dfs(x + (1 << cur), num + 1,
// cur + 2); // cur位置放国王，与它相邻的位置不能再放国王
// }
bool check(int x,int y){
if(sit[x]&sit[y])return 0;
if((sit[x]<<1)&sit[y])return 0;
if(sit[x]&(sit[y]<<1))return 0;
return 1;
}
int main(){
cin>>n>>k;
dfs(0,0,0);
for(int i=1;i<=cnt;i++){
dp[1][i][sta[i]]=1;
}
for(int i=2;i<=n;i++)
for(int j=1;j<=cnt;j++)
for(int m=1;m<=cnt;m++){
if(!check(j,m))continue;
for(int l=sta[j];l<=k;l++)dp[i][j][l]+=dp[i-1][m][l-sta[j]];
}
for(int i=1;i<=cnt;i++)ans+=dp[n][i][k];
cout<<ans<<endl;
return 0;
}