Hexo
0%

2_状态压缩dp

发表于

状态压缩dp

状态压缩dp：把每个事件标号，设成二进制下的一位数字，即用单个数字存储一个事件，这就要求每个事件只出现一次

(1)位运算

  1. 插入 A|=1<<c;
  2. 删除 A&=~(1<<c); 当确保要删除的位是1时，亦可 A^=1<<c;
  3. lowbit求二进制下最低位的1是多少 A&(-A);
  4. 清空为空集 A=0;
  5. 求并集 A|B;
  6. 求交集 A&B;
  7. 建立大小为size的全集 ALL=(1<<size)-1;
  8. 求全集中A的补集 ALL^A;
  9. 判断B是否是A的子集 (A&B)==B;
  10. 枚举所有子集情况
    1
    2
    3
    4
    for (int i=0;i<=ALL;++i)
    {
        //do something
    }
  11. 枚举A的所有子集(包括本身和空集)
    1
    2
    3
    4
    5
    int subset=A;
    {
        //do something
        subset=(subset-1)&A;
    }while(subset!=A)
  12. 求A里面有几个元素(有几个1)
    1
    2
    3
    4
    int count=0;
    for (int i=0;i<si;++i)
        if ((A&(1<<i))!=0)
            ++count;
    1
    2
    3
    int count=0;
    for (int i=0;i!=0;i>>1)
        count+=i&1;
    1
    2
    3
    4
    5
    int count=0;
    while(num!= 0){
        num=num&(num-1);
        count++;
    }
  13. highbit二进制下最高位的1
    1
    2
    3
    4
    5
    6
    7
    int p=lowbit(x);
    while (p!=x)
    {
        x-=p;
        p=lowbit(x);
    }
    return p;
  14. 判断x是否是2的幂次 return (x!=0) && (x&(x-1))==0;
  15. 判断x是否是偶数 return (x&1)==0;
  16. 判断x是否是奇数 return (x&1)==1;
  17. 求全集ALL中每个子集，设cnt[i]表示每个子集里面有几个元素
    1
    2
    3
    4
    //空集自然没有元素
    cnt[0]=0;
    for (int i=1;i<=ALL;++i)
        cnt[i]=cnt[i>>1]+(i&1);

(2)旅行商TSP问题

一张连通图，共有n个节点，从某一点除法，要求所有点至少经过一次，最后回到起始点，边权值为路径，需要满足上述条件并且总路径最小

解： dp[s][i]+w[i][j] 转移到--> dp[s|(1<<j)][j]
s表示当前已经过节点集合，s|(1<<j)表示插入新节点后的转移后的新集合，i表当前集合最后到达的节点
还可以用((1<<j)&s)==0判断新插入的节点是否不是原集合s的子集，来进行剪枝，但本题求的是min亦可不剪

(3)玉米田问题

给定一个二维0-1矩阵，”1”表示不能放东西，”0”表示能放东西，选尽量多的能放东西的格子，并且选的格子之间两两不相邻(选定一个格子a，则格子a的上下左右格子都不能选)，求最多能选多少个格子

解：可以按行从上到下枚举，这样就省去考虑下这个方向

1
2
dp[i][s]=dp[i-1][k]+cnt[s]
且 (s&k)==0 且 (s&g[i]==0) 且 (s&(s>>1))==0

i表示第i行，s表示当前操作行选取的格子的某种情况集合，i-1则表示上一行，k则表示上一行所有可能集合，cnt[s]表示当前s集合中有多少个元素，(s&k)==0保证了第i行的上这个方向不会相邻，g[i]表示第i行原始0-1矩阵的情况集合，这就保证了选择格子时不会选择”1”的格子，(s&(s>>1))==0则保证了同一行左右之间不相邻
当是m*n的矩阵问题时，可对min(m,n)进行状压，max(m,n)作转移方向