状压dp总结

· · 个人记录

（题集并非按难度由易到难排序）

状压dp是OI中一种比较暴力的dp

原理：用二进制数上的1/0表示定义状态的某个位置有/无。

题目

  1. HDU[2553]N皇后

    将列 主对角线 副对角线作为要处理的状态。 列好处理。 对角线处理时可以不必用行，直接一次一个左移一个右移，直到列的状态都是1，那么行的状态就被包含在其中了。

  2. UVA[10817]Headmaster's Headache

    记忆化搜索+状压：s1为课程只有一个老师教的 s2为课程有两个以上老师教的。 目标状态：s2都是1，ans比较记录即可。

  3. P5911PRZ

    将已经过桥的人作为状态，要过桥的人作为状态转移（这个预处理出每个状态的时耗和总重即可）。

```cpp for(int s1=s;;s1=(s1-1)&s){ ... if(!s1)break; } ``` 4. P5997 [PA2014]Pakowanie > 感性理解包从大到小装最优，设$f_{S}$为状态集合为S时的背包数，$g_{S}$是状态集合为S时的背包剩余空间。转移方程不是很难推，要注意有可能$f$一样但$g$可能更优时要更新。 5. P2150 [NOI2015]寿司晚宴 > 30pts: > 100pts: