【状压DP】易懂讲解状态压缩/状态压缩DP

状态压缩DP

状压DP 又叫集合动态规划。是以结合信息为状态的特殊的动态规划的问题。主要有传统集合动态规划和基于连通性状态压缩的动态规划两种。

状压DP和一般的DP的区别

一般的DP：着眼于整体，从中提取出几个关键信息并以此划分阶段使得问题具备无后效性或最优子性质，然后根据已知的信息依次对各个阶段进行决策。 状压DP：如果一般的状态难以描述无后效性原则，或者信息不足无法决策，许多元素的状态都直接影响的决策，都需要被考虑到。所以给每个元素都开个数组来存是行不通的。于是状压DP应运而生，它可以对多个元素的状态进行压缩存储。

状态压缩预备知识–位运算

位运算是一种速度非常快的基本运算。有很多种操作

算数左移（<<）:左移一位，相当于该数乘以$2^x$ 算数右移（>>）:右移一位，相当于该数除以$2^x$
与运算（&）:两数同一位都为$1$时结果为$1$,否则为$0$。或运算（|）:两数同一位都为$0$时结果为$0$,否则为$1$。
非运算（~）：按位取反。例如~101=010

二进制状态压缩，是指将一个长度为$m$的$bool$数组用一个$m$位$2$进制整数表示并存储的方法。利用下列位运算操作可以实现原$bool$数组中对应下标元素的存取。(注意，为了不让优先级混乱，所以建议所有长运算都加括号)