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 例题

• Codeforces 165E
• Codeforces 383E
• Codeforces 1208F