Sum over Subsets DP 入门

发布于 # algorithm

0 引

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

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

1 什么是 SOS DP

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

fmask=∑i⊆maskaif_{mask} = \sum_{i \subseteq mask} a_i

2 做法

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

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

则显然有

S(k,i)={S(k,i−1)k&2i=0S(k,i−1)∪S(k⊕2i,i−1)otherwiseS(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 例题

Comment seems to stuck. Try to refresh?✨

Woshiluo's NoteBook

「Jump up HIGH!!」