[关闭]
@xzyxzy 2018-07-20T23:41:23.000000Z 字数 807 阅读 1194

高维前缀和

动态规划

作业部落

评论地址


一、概述

高维前缀和是个好东西,很多人把它归类为状态压缩,其实听说它是由衍生出来的黑科技?

求x二进制下的超集或子集的所有状态之和怎么办?
(如超集为,子集为
高维前缀和可以把这个过程从优化到(为最大值域范围)

二、原理

通过高维前缀和的枚举顺序,可以保证枚举到第位的,所有第到末位的数的超集(子集)情况都被涵盖在内,具体原理理解请照代码手玩(博主就是靠这个理解的,但是太懒不想做表了,毕竟还有辣么多东西还没学还没总结)

枚举超集

  1. for(int j=0;j<n;j++)
  2. for(int i=0;i<1<<n;i++)
  3. if(!(i&(1<<j))) f[i]+=f[i|(1<<j)];

枚举子集

  1. for(int j=0;j<n;j++)
  2. for(int i=0;i<1<<n;i++)
  3. if(i&(1<<j)) f[i]+=f[i],f[i^(1<<j)];

这里可以自定义运算,可以取最值等等
:其实求超集就是,求子集就是

三、做题经验

1.巧用容斥

很多情况需要求的是恰好怎样的答案,这个时候可以改为至少怎样的方案,然后用容斥或者组合数容斥解决
考试2018.7.9T1、[CF449D]Jzzhu and Numbers

2.巧妙转化子集超集

可以考虑翻转后计算贡献
[SPOJ2829]Time Limit Exceeded

附录:题单

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注