Luogu P1896 [SCOI2005] 互不侵犯
因为一行的状态只有放与不放国王，所以可以用 \(0\) 和 \(1\) 表示，然后就可以把一行的状态压缩成一个 \(9\) 位二进制数表示，状态个数为 \(2^9\)。随后定义状态 \(f(i,j,s)\) 表示前 \(i\) 行放 \(j\) 个国王，最后一行状态为 \(s\) 的方案数。先 DFS 求出一行的所有状态，然后暴力枚举相邻两行的状态，判断合法性，如果合法就进行状态转移：\(f(i,j,s)=f(i-1,j-sta_{cnt1},sit_{cnt2})\)，其中 \(sta\) 存储的是每个状态摆放的国王数量，\(sit\) 存储的是每个状态，\(cnt1\)、\(cnt2\) 分别记录了第 \(i-1\) 行和第 \(i\) 行的状态编号。
最后统计答案，即为把所有摆 \(i\) 行、\(k\) 个国王的方案数累加。方案数和累加结果记得开 long long。
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int n,m,cnt;
long long ans;
int king[2010],state[2010],f[10][110][2010];
void dfs(int s,int cur,int num){if(cur>=n){state[++cnt]=num;king[cnt]=s;return ;}else{dfs(s,cur+1,num);dfs(s+(1<<cur),cur+2,num+1);}
}
bool check(int a,int b){if((king[a]<<1)&king[b]) return 0;if((king[a]>>1)&king[b]) return 0;if((king[a])&king[b]) return 0;return 1;
}
signed main(){scanf("%lld%lld",&n,&m);dfs(0,0,0);for(int i=1;i<=cnt;i++){f[1][state[i]][i]=1;}for(int i=2;i<=n;i++){for(int j=1;j<=cnt;j++){for(int k=1;k<=cnt;k++){if(!check(j,k)) continue;for(int l=state[j];l<=m;l++){f[i][l][j]+=f[i-1][l-state[j]][k];}}}}for(int i=1;i<=cnt;i++) ans+=f[n][m][i];cout<<ans;return 0;
}
至于时间复杂度，比较难估计，大概是 \(O(4^n \times nk)\)。总之 \(n\) 很小，跑得很快（实测洛谷数据 57ms，loj 还没有测）。
空间是三维的，要注意不要开太大。
Luogu P5911 [POI2004] PRZ
这个题是一道典型的枚举子集。把集合状压并预处理出每个子集所需要的最大时间 \(t_i\) 和重量 \(w_i\)，枚举所有人构成的集合 \(S\) 中的子集 \(i\) 和 \(i\) 的子集 \(j\)，那么：
\[dp_i=\min(dp_i,t_i+dp_{i \oplus j})(w_j \le W)
\]
这里枚举子集 \(j\) 不能先枚举集合再判断是否为 \(i\) 的子集，这样时间复杂度会来到 \(O(4^n)\)，过不了。应当使用 子集枚举，时间复杂度来到 \(O(3^n)\)。