[SCOI 2005] 互不侵犯

知识点

状压动态规划、棋盘模型

解题思路

枚举每行无相邻1的状态s，记录国王数。两行p、s兼容当且仅当没有上下、左斜、右斜冲突。dp[已放数][本行状态]记录方案，初态空行0，逐行转移，最后累加已放K的所有末行状态。

正确性说明

任一全棋盘合法方案，每行都无横向相邻国王，相邻两行满足三类冲突检查；反之这些局部条件覆盖国王所有八方向攻击。逐行状态记录已放总数，添加下一行是唯一分解，故转移不漏不重。

易错点

K可为0或超过可行最大值；对角冲突不能漏；答案使用64位；N=1也按通用状态处理。

复杂度

合法行状态数记S，时间O(N·K·S²)，空间O(KS)，N≤9。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n,k;cin>>n>>k;vector<int>s,c;for(int m=0;m<(1<<n);m++)if(!(m&(m<<1)))s.push_back(m),c.push_back(__builtin_popcount((unsigned)m));int S=s.size();vector<vector<long long>>d(k+1,vector<long long>(S)),v=d;d[0][0]=1;for(int row=0;row<n;row++){for(auto&a:v)fill(a.begin(),a.end(),0);for(int a=0;a<S;a++)for(int b=0;b<S;b++)if(!(s[a]&s[b])&&!(s[a]&(s[b]<<1))&&!(s[a]&(s[b]>>1)))for(int j=c[b];j<=k;j++)v[j][b]+=d[j-c[b]][a];d.swap(v);}long long ans=0;for(auto x:d[k])ans+=x;cout<<ans<<'\n';}