子集和 DP 说的是通过 DP 求出每个子集的贡献之和。也就是说,我们需要对每个 求出
其中 表示 的贡献。注意,这里的 与整个集合 有关,所以不能够直接分别对于每个元素统计它对于所有包含它的 的 的贡献。
设 表示只考虑 的后 位的子集、而剩下的位全部取的贡献之和,则显然 。此外,有转移
如果把 作为外层的循环变量,则可以用滚动数组把空间优化到 。
for (int i = 0; i < n; ++i) {
f[i] = a[i];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (1 << n); ++j) {
if (j >> i & 1) {
f[j] += f[j ^ (1 << i)];
}
}
}
参考资料: 【DP】解析 SOSdp(子集和 dp)