学习状压 dp 之前，请确认你已经完成了 动态规划基础 部分内容的学习。
（同时建议学习 位运算 部分的内容）
状压 dp 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。
???+note "「SCOI2005」互不侵犯"
在 $N\times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。
我们用 $f(i,j,l)$ 表示只考虑前 $i$ 行，第 $i$ 行按照编号为 $j$ 的状态放置国王，且已经放置 $l$ 个国王时的方案数。
对于编号为 $j$ 的状态，我们用二进制整数 $sit(j)$ 表示国王的放置情况，$sit(j)$ 的某个二进制位为 $0$ 表示对应位置不放国王，为 $1$ 表示在对应位置上放置国王；用 $sta(j)$ 表示该状态的国王个数，即二进制数 $sit(j)$ 中 $1$ 的个数。例如，如下图所示的状态可用二进制数 $100101$ 来表示（棋盘左边对应二进制低位），则有 $sit(j)=100101_{(2)}=37, sta(j)=3$。
我们需要在刚开始的时候枚举出所有的合法状态（即排除同一行内两个国王相邻的不合法情况），并计算这些状态的 $sit(j)$ 和 $sta(j)$。
设上一行的状态编号为 $x$，在保证当前行和上一行不冲突的前提下，枚举所有可能的 $x$ 进行转移，转移方程：
$$
f(i,j,l) = \sum f(i-1,x,l-sta(j))
$$
??? "参考代码"
cpp --8<-- "docs/dp/code/state/state_1.cpp"
NOI2001 炮兵阵地
「USACO06NOV」玉米田 Corn Fields
九省联考 2018 一双木棋
UVA10817 校长的烦恼 Headmaster's Headache
UVA1252 20 个问题 Twenty Questions
