本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-21 20:56:05

这两道题都是状态压缩的题目。

P1879 [USACO06NOV] Corn Fields G

我们知道，对于一个状态 j，为了使它每一个 $1$ 之间不相邻，我们有 j & (1 << j) 为零。而要使它与前一行的状态 $k$ 不冲突，我们需要有 j & k 为零。

这就告诉我们怎么进行状态之间的转移。我们设 $f(i, j)$ 表示第 $i$ 行，状态为 $j$ 的时候的方案数。我们知道，$f(i, j)$ 可以由 $f(i - 1, k) \text{ s.t. } k \text{&} j = 0$ 转移而来，其中 $k$ 表示的是前一行的状态。

最终，我们有

$$ f(i,j) = \begin{cases} 0 & i = 0, j = 0\ \sum\limits_{k & j = 0} f(i-1,k) & \text{otherwise} \end{cases} $$

最终我们要统计的就是第 $m$ 行所有状态的方案数量和。

P1171 售货员的难题

旅行商问题嘛。依然是设状态 $f(i, j)$， 表示由状态 $j$ 走到第 $i$ 个点的最短距离，其中 $i \notin j$。

我们如果知道了 $f(i, j)$，就可以推出 $f(i, j\cup \{k\}) = f(i,j) + P_{j, k}$。归纳边界 $f(0, 1) = 0$。

我们要求的就是在最终的满状态里选一点，从这一点走到 $0$，找最小值。