Contest1110 - 状态压缩DP

对于“状态压缩动态规划”中的状态，通常与集合相关联。集合本身具有三个性质：确定性，互异性和无序性 。这也就决定了只关心每个元素的存在状态，而这通常可以使用 0 或者 1 表示存在 或者不存在。例如，一顿饭有 8 道菜，小明同学最终吃了某几道菜，必然是这 8 道菜的子集。令 1 表示吃了， 0 表示没吃，那么以下几个状态：10000001 表示只吃了 1 号菜和 8 号菜； 01010101 表示吃了 2 , 4 , 6 , 8 四道菜。

由此可见，可以通过一串 01 码来清晰地表示一个集合的状态。同时，在确定了最低位的前 提下，一串 0-1 码与一个二进制数一一对应。这种表示状态的方式被称为状态压缩，简称状压。所谓“压缩”，即是用一个二进制数来保存一组状态，将一个集合的状态压缩进了一个二进制数中，而通常这个二进制数在十进制下的大小可以作为其编号。状态压缩本质上是进行了两步操作：

1. 给这个集合的每个状态一个编号；
   
2. 通过该编号，轻易地访问该状态。