关于状态压缩DP的学习

废话

Oveln发现自己的状压dp极其弱爆

然后看了看历年的NOIPTG的试题,连续两年状压DP使Oveln开始慌了

于是打算颓一段时间的状压

适用范围

大概就是那种可以将题目中的状态压缩成一段01串+某几个条件的题目

关于状态压缩的技巧

  1. 关于一个状态w所表示的01串,查询第k位是否为1,也就是该状态是否存在第k个元素,((1<<k)&w)
  2. 关于一个状态w是否是另一个状态m的子状态,即w状态的元素集合是否是m状态的元素集合的子集,((w|m)==m)
  3. 关于一个状态 w和另一个状态m的元素集合的交集(w&m),并集(w|m)
  4. 关于一个状态w的元素集合和另一个状态m的元素集合的补集(w^m)
  5. 枚举一个状态w的子集 for (int s0=w-1;s0;s0=(s0-1)&w){…}
  6. 对于一个问题,设该问题的状态元素的个数为n,则该问题的所有状态的子集数量和 3^n(证明在下)

关于上一块第6点的证明

元素有x个的状态有C^x_n,元素有x个的状态的子集有2^x

则元素的状态的子集数量和为\sum C^x_n*2^x

根据二项式定理\sum C^x_n*2^x=(2+1)^n=3^n

“关于状态压缩DP的学习”的2个回复

发表评论

电子邮件地址不会被公开。