@xzyxzy
2018-07-21T07:41:23.000000Z
字数 807
阅读 3091
动态规划
高维前缀和是个好东西,很多人把它归类为状态压缩,其实听说它是由衍生出来的黑科技?
求x二进制下的超集或子集的所有状态之和怎么办?
(如超集为,子集为)
高维前缀和可以把这个过程从优化到(为最大值域范围)
通过高维前缀和的枚举顺序,可以保证枚举到第位的,所有第到末位的数的超集(子集)情况都被涵盖在内,具体原理理解请照代码手玩(博主就是靠这个理解的,但是太懒不想做表了,毕竟还有辣么多东西还没学还没总结)
for(int j=0;j<n;j++)
for(int i=0;i<1<<n;i++)
if(!(i&(1<<j))) f[i]+=f[i|(1<<j)];
for(int j=0;j<n;j++)
for(int i=0;i<1<<n;i++)
if(i&(1<<j)) f[i]+=f[i],f[i^(1<<j)];
这里可以自定义运算,可以取最值等等
:其实求超集就是,求子集就是
很多情况需要求的是恰好怎样的答案,这个时候可以改为至少怎样的方案,然后用容斥或者组合数容斥解决
考试2018.7.9T1、[CF449D]Jzzhu and Numbers
可以考虑翻转后计算贡献
[SPOJ2829]Time Limit Exceeded