9

Sum over Subsets DP 入门

 2 years ago
source link: https://blog.woshiluo.com/2073.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Sum over Subsets DP 入门

2022年4月4日2022年4月4日 by woshiluo

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

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

1 什么是 SOS DP

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

fmask=∑i⊆maskai

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

定义 S(k,i)={x|x⊆k∧k⊕x<2i+1}。

S(k,i)={S(k,i−1)k&2i=0S(k,i−1)∪S(k⊕2i,i–1)otherwise

注意到现在已经可以递推 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 ) ];
    }
}

class

OI

local_offer

dp

有3条评论

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK