【动态规划】SOSdp

SOSdp是关于集合的特殊动态规划

• 子集和$dp: dp(st,i)$ 表示集合$st$ 的最后$i$ 位变化的所有子集的贡献

• 第$i$ 位为$0$ ，$dp(st,i)=dp(st,i-1)$

• 第$i$ 位为$1$ ，$dp(st,i)=dp(st,i-1)+dp(st\wedge (1<<i),i-1)$

• 压缩掉一维，变成如下代码

for (int j = 0; j < n; j++)
    for (int i = 0; i < 1 << n; i++)
        if (i >> j & 1)
            f[i] += f[i ^ (1 << j)]; // i在j-1层

• 应用
  • 高维前缀和