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

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

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

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

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

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

给定一张 n n n个点的带权无向图，点从 0 ∼ n − 1 0 sim n−1 0∼n−1标号，求起点 0 0 0 到终点 n − 1 n−1 n−1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 0 0到 n − 1 n−1 n−1不重不漏地经过每个点恰好一次。

分析：不重不漏的经过一个带权无向图，这就是著名的NP-Complete问题的一个经典问题–TSP。那么对于这样一类没有多项式算法的问题，搜索算法（时间复杂度为 O ( n ! ) O(n!) O(n!)）并非是一个解决问题的唯一途径。

不难发现我们只需要知道**（1）哪个点被用过。（2）目前停在哪个点上。**DP问题崭露头角。我们同时发现任何时候我们只需要知道哪些点已经被遍历过而遍历点耳朵具体顺序对以后的决策是没有影响的。至此，我们的状态已经出现了。

设 s t a t e state state为状态。则有 f [ s t a t e ] [ j ] = f [ s t a t e _ k ] [ k ] + w [ k ] [ j ] f[state][j]=f[state_k][k]+w[k][j] f[state][j]=f[state_k][k]+w[k][j]，其中 s t a t e _ k = s t a t e 是 包 含 k 且 除 掉 j 之 后 的 集 合 state_k=state是包含k且除掉j之后的集合 state_k=state是包含k且除掉j之后的集合。我们用二进制来表示 s t a t e state state，如果这个点存在则为 1 1 1，不存在则为 0 0 0。则 s t a t e state state=( i i i>> j j j) & 1 &1 &1，意为 i i i右移 j j j位，通俗一点说就是将 i i i移到个位上再 & 1 &1 &1，就可以取出 i i i的第 j j j位。如果 s t a t e = 1 state=1 state=1则合法，反之不合法。我们以同样的思想就可以实现 s t a t e _ k = i − ( 1 state_k=i-(1 state_k=i−(1<< j ) j) j)>> k & 1 k&1 k&1，本题得到解决。

#include 
using namespace std;
long long n,f[1<<20][21],w[1000][1000];
int main(){
    memset(f,0x3f,sizeof(f));
    cin>>n;
    for(int i=0;i>w[i][j];
    f[1][0]=0;//初始状态，第1个点被用过，目前停在第0个点上，等于0 
    for(int i=1;i<(1<>j&1)
            for(int k=0;k>k&1)  f[i][j]=min(f[i][j],f[i^(1< 
二进制下不进位的应用 
例题：起床困难综合症 
给定
    
     
      
       
        n
       
       
        ,
       
       
        m
       
      
      
       n,m
      
     
    n,m以及
    
     
      
       
        n
       
      
      
       n
      
     
    n个数和该数所对应的运算，其中运算有 与、或、异或 三种，问在所有不大于
    
     
      
       
        m
       
      
      
       m
      
     
    m的非负整数中，对给定的
    
     
      
       
        n
       
      
      
       n
      
     
    n个数都按该数所对应的运算运算一遍后，能得到得最大的值是多少。AND 表示按位与，OR 表示按位或，XOR 表示按位异或
 
输入样例：
 
3 10
AND 5
OR 6
XOR 7
 
输出样例：
 
1
 
注意到按位与、按位或、按位异或共有的一个性质：每次运算只有关该位上的数，不影响其它位上的数
 所以我们可以从高位到低位来确定数的每一位。
 如果该位可以填
    
     
      
       
        u
       
      
      
       u
      
     
    u，并且填
    
     
      
       
        u
       
      
      
       u
      
     
    u之后答案的该位是
    
     
      
       
        1
       
      
      
       1
      
     
    1，那么在该位填 
    
     
      
       
        u
       
      
      
       u
      
     
    u，否则填
    
     
      
       
        !
       
       
        u
       
      
      
       !u
      
     
    !u
 那么如何判断该位能填几呢？如果该位填
    
     
      
       
        1
       
      
      
       1
      
     
    1后，所得到的数大于
    
     
      
       
        m
       
      
      
       m
      
     
    m，那么该位填
    
     
      
       
        !
       
       
        u
       
      
      
       !u
      
     
    !u
 否则如果该位填
    
     
      
       
        1
       
      
      
       1
      
     
    1后，所得到的数对
    
     
      
       
        n
       
      
      
       n
      
     
    n个数都运算之后，结果小于等于该位填
    
     
      
       
        0
       
      
      
       0
      
     
    0后得到的结果，那么为了让剩下能填的数更大，该位填
    
     
      
       
        0
       
      
      
       0
      
     
    0。否则该位填
    
     
      
       
        1
       
      
      
       1
      
     
    1。
 
由于我们只需要得到填出来的数对所有数运算后的结果，而并不需要输出填出来的数，所以在写代码的时候并不需要真正的把数填出来，只需要确定是否能将答案的该位填成 
    
     
      
       
        1
       
      
      
       1
      
     
    1即可
 一共要判断
    
     
      
       
        l
       
       
        o
       
       
        g
       
       
        ⁡
       
       
        m
       
      
      
       log⁡m
      
     
    log⁡m次，每次判断是
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)的，所以总的时间复杂度是 
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        l
       
       
        o
       
       
        g
       
       
        m
       
       
        )
       
      
      
       O(nlogm)
      
     
    O(nlogm)
 
#include 
const int N=100005;
int n,m,ans,t[N],op[N];        
char str[4];
bool calc(bool x,int j){    // calc用于计算 x 经过所有数的第 j 位操作后所得到的结果
    for(int i=0;i>j&1); 
        else if(op[i]==2) x=x^(t[i]>>j&1); 
        else x=x&(t[i]>>j&1);           
    return x;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=0;i
        scanf("n%s%d",str,t+i);
        if (*str=='O') op[i]=1;
        else if(*str=='X') op[i]=2;    
        else op[i]=3;
    }
    for (int i=29;~i;i--)                  
	  // 因为本题中m最大是10^9,log2(10^9)=3log2(10^3)<3*10=30所以每次i从29往后枚举就可以了
      if(1<           // 如果填 1 后小于等于 m，要看填完后对答案的影响来填
        bool x=calc(0,i),y=calc(1,i); //先分别处理出该位填 0 的结果和该位填 1 的结果
        if (x>=y) ans=ans|(x< 
STL bitset运用 
一、概念
 
    
     
      
       
        b
       
       
        i
       
       
        t
       
       
        s
       
       
        e
       
       
        t
       
      
      
       bitset
      
     
    bitset可以说是一个多位二进制数，每八位占用一个字节，因为支持基本的位运算，所以可用于状态压缩，
    
     
      
       
        n
       
      
      
       n
      
     
    n位
    
     
      
       
        b
       
       
        i
       
       
        t
       
       
        s
       
       
        e
       
       
        t
       
      
      
       bitset
      
     
    bitset执行一次位运算的时间复杂度可视为
    
     
      
       
        n
       
       
        /
       
       
        32
       
      
      
       n/32
      
     
    n/32.
 
二、基本操作
 
bitset s;
//表示一个n位的二进制数，<>中填写位数；
a.size()返回大小（位数）    a.count()返回1的个数
a.any()返回是否有1         a.none()返回是否没有1
a.set()全都变成1           a.set(p)将第p+1位变成1
a.set(p, x)将第p+1位变成x  a.reset() 全都变成0
a.reset(p)将第p+1位变成0   a.flip()全都取反
a.flip(p)将第p+1位取反     a.to_ulong() 返回它转换为ul的结果，如果超出范围则报错
a.to_ullong()返回它转换为ull的结果，如果超出范围则报错 a.to_string()返回它转换为string的结果
a.test() 获得指定位的值
 
s=101;// 存储为0001100101
cout< 
例题：【bitset】无穷的序列 
有一个无穷序列如下：110100100010000100000…请你找出这个无穷序列中指定位置上的数字。
 
第一行一个正整数N，表示询问次数；接下来的N行每行一个正整数Ai，Ai表示在序列中的位置。
 
#include //板子题
using namespace std;
const int N=1e8;
bitsets;
int idx=1,n;
int main(){
	for(int i=0;idx<=N;idx+=i++) s[idx]=1;
	scanf("%d",&n);
	while(n--){
		int x;scanf("%d",&x);
		printf("%dn",s.test(x));
	}
	return 0;
}

 
用bitset做“起床困难综合症” 
#include
using namespace std;
int n,m,ans=0;
int main(){
    bitset<40> none,one ;
    none.reset(); // 一个初始化每一位都是0
    one.set();    // 一个初始化每一位都是1
    cin>>n>>m ;
    while(n--){
        string x;int y;
        cin>>x>>y;
        if(x=="AND") none&=y,one&=y;
        else if(x=="OR") none|=y,one|=y;
        else none^=y,one^=y;
    }
    for(int i=0;i<31;i++){
        if(none[i]==1) ans+=(1<=(1<