P1879 [USACO06NOV] Corn Fields G & P1171 售货员的难题
__ryp__
·
·
个人记录
这两道题都是状态压缩的题目。
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，找最小值。