前言
依旧学啥写啥，话说现在不实名还能发吗？
施工ing
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文
前言-位运算
> 此处只解析状压DP可能使用的位运算。
运算符
> 需要注意的是，除取反外的位运算符优先级低于算术运算符，而按位于，按位或，异或优先级低于比较运算符。[1]
移位：A << B左移或A >> B右移
将二进制a移位b位。（详细的移位内容详见运算 - OI Wiki - 位运算符）
如：
注意到左移时低位用0填充，移位溢出位舍去。
按位运算符 & |
按位与& 和按位或 | 接收两个操作数，并对其按每一位进行与/或操作。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
什么是状态压缩动态规划
> 状压 DP 是动态规划的一种，通过将状态集合转化为整数记录在 DP 状态中来实现状态转移的目的．
> 为了达到更低的时间复杂度，通常需要寻找更低状态数的状态．大部分题目中会利用二元状态，用nnn位二进制数表示nnn个独立二元状态的情况．
> ——OI Wiki[2]
通俗来讲，状压DP通过使用二进制表示状态。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
状压DP的核心思路和操作
通过上面的介绍我们可以知道状压DP通过二进制表示状态。那么要对这些状态进行运算和转移，我们就需要使用位运算。
假设这是一个二进制数字：
01101010
获取位
我们现在要获取这个数字的第444位。
> 在二进制中，位一般从右往左从低到高，最低位（最右边的位）为第111位。
首先，我们创建一个这样的二进制数字：
00000001
然后把这个数字左移4−1=34-1=34−1=3位：
00001000
然后把这个数字和原数做一个按位与：
01101010
00001000
得到
00001000
当作bool类型运算的话答案为1。
如果对01100010做相同运算，答案则为0。
据此总结获取a第b位的操作如下：
修改位
> 还有位操作版本，个人认为此版本更方便。
还是上面那个数字，我们现在要把这个数的第333位设置为1。
首先我们要确认这个数字的第333位为0，显然是的。
然后我们还是同样操作创建一个第333位为1的数：
00000100
然后在原数基础上+这个数字：
01101010
00000100
得到
01101110
我们可以得到将某一位设置为0的话，先确认这位是1然后减去即可。
代码如下（a的第b位设置为1）：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题
P3052 [USACO12MAR] Cows in a Skyscraper G / A90642.Cows in a Skyscraper G
想法
注意到对于每一头牛都有放了/没放两种状态，可以使用二进制表示。我们考虑状压DP。
据此设计出状态：
dp[i]表示对于二进制状态i最少使用的电梯数量。
显然当i=0i=0i=0时不使用任何电梯，然而我们必须“留”一辆电梯让后续的状态可以转移，所以我们令初始状态为：
dp[0]=1，即没有牛上电梯的时候使用1辆电梯。
同时，最终答案的i是：
1111..<一共n个1>..111，表示nnn头牛全部坐电梯下楼。
那么要获取这个值，我们发现这个值+1+1+1的值等于100000..<n个0>..000，刚好是1<<n的值。
因此，最终答案是：
dp[(1<<n)-1]，也就是当所有牛全部坐了电梯。
啊对，还要新建一个数组存储当前电梯的已载重。
然后对于转移，考虑从当前状态为基础，减去一头牛。
那么就要枚举减去的这头牛i。
首先，如果当前状态没有这头牛，那么跳过。
然后，创建一个转移到当前状态的前向状态，赋值为从当前状态减去一个第i位是1，其他为0的数，也就是把这位设置成0。
更新有两种可能：
1. 前向状态的使用电梯数量小于当前电梯数量，更新。
对于这个状态，如果前向的电梯载重加上当前牛的重量大于最大载重，那么要新一台电梯。
2. 前向状态电梯数量等于当前且不需要新的电梯，更新。
更多细节见代码。
AC CODE
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
引用
位运算操作符：https://oi-wiki.org/lang/op/#位操作符
位操作：https://oi-wiki.org/math/bit
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 见https://oi-wiki.org/lang/op/#位操作符。 ↩︎
2. https://oi-wiki.org/dp/state/#简介 ↩︎
