Sum over Subsets DP 入门

0 引

为什么没在标题里写 SOS DP ?因为这 SOS 这个名字我第一次看的时候怎么看怎么觉得不正经,所以写全称让他看着正经一些。

个人感觉这个东西更像是一个套路而不是 DP 类型。

1 什么是 SOS DP

Sum over Subsets DP,即求子集和的 DP。更具体的说,用于在 $O(k \cdot 2^k)$ 的时间求出以下式子:

$$
f_{mask} = \sum_{i \subseteq mask} a_i
$$

2 做法

一种非常朴素的方式是直接对于每个子集枚举其子集,复杂度是 $O(4^n)$。这个复杂度显然是无法接受的。

定义 $S(k,i) = \{ x | x \subseteq k \land k \oplus x < 2^{i+1} \}$。

则显然有

$$
S(k,i) =
\begin{cases}
S(k,i-1) & k \& 2^i = 0 \\
S(k,i-1) \cup S( k \oplus 2^i, i – 1 ) & otherwise
\end{cases}
$$

注意到现在已经可以递推 S 来得到我们想要的结果了。

但是更广为人知的是这个滚动数组的写法:

for( int st = 0; st < ( 1 << K ); st ++ )
    f[i] = a[i];
for( int j = 0; j < K; j ++ ) {
    for( int st = 0; st < ( 1 << K ); st ++ ) {
        if( st & ( 1 << j ) ) 
            f[i] += f[ i ^ ( 1 << j ) ];
    }
}

3 例题

4 thoughts on “Sum over Subsets DP 入门

  • […] SOS DP 求出每个集合是否有数字是其子集即可。 […]

  • […] 注意到基本上是 SOS DP 的模版,除一个问题 — 对于一个字符串可能会被统计多次。 […]

  • […] $a_j\&a_k$,显然可以通过 SOS DP 来求出对于任意 $s$,其最靠后 $j$ 的能够有 $k$ 使得 $s subseteq a_j\&a_k$ […]

  • […] 一种比较野蛮的办法是参见 Sum over Subsets DP 的证明,这个东西实际上就是以质数为轴的高维前缀和。 […]

  • 发表回复

    您的电子邮箱地址不会被公开。 必填项已用*标注

    message
    account_circle
    Please input name.
    email
    Please input email address.
    links

    此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据